求和（1,2,3.....n使其和为m的所有情况）-蒲公英云

求和（1,2,3.....n使其和为m的所有情况）

输入两个整数 n 和 m，从数列1，2，3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来

输入描述:

每个测试输入包含2个整数,n和m

输出描述:

按每个组合的字典序排列输出,每行输出一种组合

示例1

输入

5 5

输出

1 4

2 3

5

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
void find_ans(vector<int> ret, int cur_pos, int n, int cur_sum, int sum) {
    if (cur_pos >= n) return ;
    cur_sum += v[cur_pos];
    ret.push_back(v[cur_pos]);
    if (cur_sum == sum) {
        for (int i = 0; i < ret.size() - 1; ++i) {
            cout << ret[i] << " ";
        }
        cout << ret[ret.size() - 1];
        cout << endl;
        return ;
    } else if (cur_sum > sum) { // 大于sum，就没必要再继续往下了，剪枝操作
        return ;
    }
    // 把当前的下标位置的值放进去，继续下一个位置
    find_ans(ret, cur_pos+1, n, cur_sum, sum);
    // 不要当前值，从下一个位置搜索，意思大概就是不从1开始找了，从2开始找
    vector<int>::iterator it = ret.end();
    --it;
    ret.erase(it);
    find_ans(ret, cur_pos+1, n, cur_sum - v[cur_pos], sum);
    // 总体思想就是当前位置的数是要还是不要的事情，列出来所有的可能，挨个输出就行了
}
int main() {
    int n, num;
    cin >> n >> num;
    for (int i = 0; i < n; ++i) {
        v.push_back(i+1);
    }
    // 因为如果n大于num的话，那么num后面的数字肯定不需要再考虑了，所以我们只需要考虑从1~num之间的可能组合就行了
    if (n >= num) n = num;
    vector<int> ret;
    int sum = 0;
    // 利用递归的方法来做，0是当前位置，n是最大下标，sum是当前和，num就是要求的结果
    find_ans(ret,0,n,sum,num);
    return 0;
}