dfs真的好难哦。
递归真的好难哦。
这道题用dfs+回溯逐个遍历结果集。
通过不断的遍历每一个结果,然后求解。建议按照代码在脑子里走一遍。
#include<iostream> #include<vector> using namespace std; vector<int> vec; int m,n; void dfs(int index,int sum){ if(sum>m)return ; if(sum==m){ for(int i=0;i<vec.size()-1;i++){ cout<<vec[i]<<" "; }cout<<vec[vec.size()-1]<<endl; } for(int i=index;i<=n&&sum+i<=m;i++){ //sum+i<=m剪枝 vec.push_back(i); dfs(i+1,sum+i); vec.pop_back(); //回溯 } } int main(){ while(cin>>n>>m){ dfs(1,0); vec.clear(); } return 0; }