题解 | #求和#

1. 这是求和得常用DFS回溯套路

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& ans, vector<int> &res,int index, int sum, int target,int end){

    //base case
    if(sum==target){
        for(int i=0;i<res.size()-1;i++){
            cout<<res[i]<<" ";
        }
        cout<<res[res.size()-1]<<endl;
        return;
    }


    for(int i = index; i<=end && sum+i <= target;i++){ //sum+i<=m剪枝
        res.push_back(i);
        dfs(ans,res, i + 1 , sum+i ,target,end);
        res.pop_back();//回溯
    }



}



int main(){
    int n,m;

    while(cin>>n>>m){

        vector<vector<int>> ans;
        vector<int> res;

        dfs(ans,res,1,0,m,n);
        res.clear();


    }


    return 0;
}