题解 | 求和

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(int n, int m, int start, vector<int>& current_combination, vector<vector<int>>& results) {
        if (m == 0) {
            results.push_back(current_combination);  // 记录当前组合
            return;
        }
        for (int i = start; i <= n; i++) {
            if (i > m) break;  // 如果当前数字大于剩余的m，直接返回
            current_combination.push_back(i);  // 选择当前数字
            backtrack(n, m - i, i + 1, current_combination, results);  // 递归
            current_combination.pop_back();  // 撤销选择
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Solution solution;
    vector<vector<int>> results;
    vector<int> current_combination;
    
    solution.backtrack(n, m, 1, current_combination, results);
    
    for (const auto& combination : results) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;  // 输出结果
    }
    
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static class Solution {
        public void backtrack(int n, int m, int start, List<Integer> currentCombination, List<List<Integer>> results) {
            if (m == 0) {
                results.add(new ArrayList<>(currentCombination));  // 记录当前组合
                return;
            }
            for (int i = start; i <= n; i++) {
                if (i > m) break;  // 如果当前数字大于剩余的m，直接返回
                currentCombination.add(i);  // 选择当前数字
                backtrack(n, m - i, i + 1, currentCombination, results);  // 递归
                currentCombination.remove(currentCombination.size() - 1);  // 撤销选择
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        Solution solution = new Solution();
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();
        
        solution.backtrack(n, m, 1, currentCombination, results);
        
        for (List<Integer> combination : results) {
            for (int num : combination) {
                System.out.print(num + " ");
            }
            System.out.println();  // 输出结果
        }
        
        sc.close();
    }
}

def backtrack(n, m, start, current_combination, results):
    if m == 0:
        results.append(current_combination[:])  # 记录当前组合
        return
    for i in range(start, n + 1):
        if i > m:  # 如果当前数字大于剩余的m，直接返回
            break
        current_combination.append(i)  # 选择当前数字
        backtrack(n, m - i, i + 1, current_combination, results)  # 递归
        current_combination.pop()  # 撤销选择

if __name__ == "__main__":
    n, m = map(int, input().split())
    results = []
    backtrack(n, m, 1, [], results)
    
    for combination in results:
        print(" ".join(map(str, combination)))  # 输出结果