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

柔光的暖阳◎ 2022-06-10 08:40 192阅读 0赞

输入两个整数 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;
    }