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],
]
C++:
01 void combine_help(int n, int index, int k, vector<vector<int>>& v, vector<int> cur)
02 {
03     if(k==0){
04         v.push_back(cur);
05         return;
06     }
07     if(index>n)
08         return;
09     combine_help(n,index+1,k,v,cur);
10     cur.push_back(index);
11     combine_help(n,index+1,k1,v,cur);
12 }
13 
14 vector<vector<int> > combine(int n, int k)
15 {
16     vector<vector<int>> result;
17     vector<int> cur;
18     if((k<=0)||(n<=0))
19         return result;
20     combine_help(n,1,k,result,cur);
21     return result;
22 }
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s