解决思路
- 深度优先搜索 (DFS):使用 DFS 枚举所有可能的骰子点数组合。
- 剪枝:在 DFS 过程中,如果当前点数和已经超过 sum 或者剩余骰子无法达到 sum,则剪枝。
- 字典序输出:由于 DFS 的递归顺序,天然保证了字典序输出。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e3+10; // 定义常量N,表示数组的最大长度 int n, sum; // n表示骰子的个数,sum表示目标点数和 int a[N], k; // a数组用于存储当前的骰子点数组合,k表示当前已经选择的骰子个数 // 打印当前组合 void print() { for(int i = 1; i <= k; i++) cout << a[i]; // 输出当前组合的每个骰子点数 cout << endl; // 换行 } // 深度优先搜索函数 void dfs(int cnt, int s) { if(k == n) { // 如果已经选择了n个骰子 if(s == sum) print(); // 如果当前点数和等于目标点数和,则打印当前组合 return; // 返回上层调用 } for(int i = 1; i <= 6; i++) { // 枚举当前骰子的点数,从1到6 a[++k] = i; // 将当前点数加入组合 dfs(cnt + 1, s + i); // 递归调用,继续选择下一个骰子 k--; // 回溯,移除当前点数 } } int main() { cin >> n >> sum; // 读取骰子的个数和目标点数和 dfs(0, 0); // 从第0个骰子开始,当前点数和为0,开始深度优先搜索 return 0; // 返回0,表示程序正常结束 }