top1编程
← 返回题目
题解

【基础】自然数的分解

1 条题解

  • 0
    @ 2026-7-29 0:15:12
    #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