## Saturday, January 26, 2013

### [LeetCode] Combinations, Solution

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],
]
```
» Solve this problem

[Thoughts]
Similar as "Conbination Sum". But here the terminate condition is "k", not sum.

[Code]
``````1:    vector<vector<int> > combine(int n, int k) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<vector<int> > result;
5:      vector<int> solution;
6:      GetCombine(n,k,1, solution, result);
7:      return result;
8:    }
9:    void GetCombine(
10:      int n,
11:      int k,
12:      int level,
13:      vector<int>& solution,
14:      vector<vector<int> >& result)
15:    {
16:      if(solution.size() == k)
17:      {
18:        result.push_back(solution);
19:        return;
20:      }
21:      for(int i =level; i<= n; i++)
22:      {
23:        solution.push_back(i);
24:        GetCombine(n,k,i+1, solution, result);
25:        solution.pop_back();
26:      }
27:    }
``````