题解 | 求和

求和

https://www.nowcoder.com/practice/11cc498832db489786f8a03c3b67d02c

解题思路

回溯法：使用回溯算法生成所有可能的组合。
递归：在递归过程中，选择当前数字或不选择，直到达到目标和m。
字典序：由于我们从小到大选择数字，生成的组合自然是按字典序排列的。

关键点：

使用回溯法生成组合。
维护当前和，判断是否达到目标。
使用列表存储当前组合，达到目标时输出。

算法步骤：

定义一个回溯函数，接受当前数字、当前和和当前组合。
在回溯函数中，遍历从当前数字到n的所有数字。
如果当前和加上当前数字小于等于m，则将当前数字加入组合并递归调用。
如果当前和等于m，则输出当前组合。
递归返回后，移除最后一个数字以尝试其他组合。

代码

cpp
java
python

#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)))  # 输出结果