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  };

Loading Disqus comments...
Table of Contents