combinations
combinations
Easy problem using DFS
This problem is same like subsets, put an element in a vector, and find the combinations of the rest elements with lenght-1.
1 class Solution {
2 private:
3 vector< vector< int > > result;
4 public:
5 vector<vector<int> > combine(int n, int k) {
6 result.clear();
7 if ( k == 0 || n < k ) {
8 return result;
9 }
10 vector< int > t;
11 t.clear();
12 DFS(1,n,k,t);
13 return result;
14 }
15 void DFS( int start, int end, int len, vector< int >& t ) {
16 if ( 0 == len ) {
17 result.push_back(t);
18 }
19 for( int i = start; i <= end; i++ ) {
20 t.push_back(i);
21 DFS(i+1,end,len-1,t);
22 t.pop_back();
23 }
24 }
25 };