首页 > 代码库 > Combinations
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]思路：使用DFS求解即可。对于每个元素存在两种选择：取和不取。若当前剩余元素的个数等于还需要取的元素的个数，则后面的元素都必须取。
1 class Solution { 2 public: 3 vector<vector<int>> combine( int n, int k ) { 4 vector<int> combination; 5 DFS( combination, 0, k, n ); 6 return result; 7 } 8 private: 9 void DFS( vector<int> &combination, int i, int k, const int &n ) {10 if( k == 0 ) { result.push_back( combination ); return; }11 if( n-i == k ) {12 vector<int> tmp = combination;13 for( int val = i+1; val <= n; ++val ) { tmp.push_back( val ); }14 result.push_back( tmp );15 } else if( n-i > k ) {16 DFS( combination, i+1, k, n );17 combination.push_back( i+1 );18 DFS( combination, i+1, k-1, n );19 combination.pop_back();20 }21 return;22 }23 vector<vector<int>> result;24 };
Combinations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。