求子集合C(n,k)问题;---DFS
vector<vector<int> > combine(int n, int k) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<vector<int> > result; if(n<=0||k<0||k>n) return result; vector<int> set; subset(0,n,k,set,result); return result; } void subset(int curPos,int& n,int& k,vector<int>& set, vector<vector<int> >& result) { if(set.size()==k) { result.push_back(set); return; } for(int i=curPos;i<n;i++) { set.push_back(i+1); subset(i+1,n,k,set,result); set.pop_back(); } }
另外一种写法:更好理解
vector<vector<int> > combine(int n, int k) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> temp; vector<vector<int> > ans; combine_rec(ans , temp , n , k , 1); return ans; } void combine_rec(vector<vector<int> > &ans , vector<int> temp , int n , int k , int index) { if (k == 0) ans.push_back(temp); else if (k > 0 && index <= n) { temp.push_back(index); //选择了index combine_rec(ans , temp , n , k-1 , index+1); //注意k-1 temp.pop_back(); combine_rec(ans , temp , n , k , index+1); //不选择index,注意是k } }
原文链接: https://www.cnblogs.com/summer-zhou/p/3248109.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/99302
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!