题解
【基础】自然数的分解
1 条题解
-
0
#include <iostream> #include <vector> using namespace std; int n; vector<int> path; // remaining: 剩余需要凑的数 // start: 当前这一步最小可以选的数(保证非递减) void dfs(int remaining, int start) { if (remaining == 0) { // 题目样例暗示不包含自身单独作为一项(如3不输出3,7不输出7) // 如果path长度大于1,或者虽然长度为1但该数不等于原始n(这在逻辑上不可能,因为如果长度为1且和为n,那这个数就是n) // 根据样例,只输出长度 >= 2 的组合,或者理解为真拆分。 // 实际上,如果我们在第一层循环限制 i < n,就可以避免 [n] 这种情况。 // 这里我们采用输出时判断,或者更常见的:题目通常隐含至少两个数。 // 观察样例:3 -> 1+1+1, 1+2. 没有 3. // 7 -> ... 没有 7. // 所以如果 path 大小 >= 2 才输出? // 等等,如果 n=1? 题目说 n<=20 自然数。如果 n=1,无解? // 让我们看递归逻辑。如果我们在主函数调用 dfs(n, 1),并在 dfs 内部遍历。 // 为了避免输出 [n],我们可以要求 path 非空且 (path.size() > 1 || path[0] != n) ? // 最简单的办法:在第一次调用时,限制最大选取的数为 n-1。 if (path.size() > 0) { for (int i = 0; i < path.size(); ++i) { if (i > 0) cout << "+"; cout << path[i]; } cout << endl; } return; } for (int i = start; i <= remaining; ++i) { // 如果是第一层(path为空),且 i == n,则跳过,以避免输出 "n" 本身 // 但更通用的写法是:只要 remaining == n 且 path 为空,i 只能取到 n-1 if (path.empty() && i == n) { continue; } path.push_back(i); dfs(remaining - i, i); path.pop_back(); } } int main() { if (cin >> n) { dfs(n, 1); } return 0; }
- 1