[Leetcode 63] 77 Combinations

Problem:

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],
]

Analysis:

Simple backtracking problem.

Code:

 1 class Solution {
 2 public:
 3     vector<vector<int> > res;
 4     int kk;
 5     int nn;
 6     
 7     vector<vector<int> > combine(int n, int k) {
 8         // Start typing your C/C++ solution below
 9         // DO NOT write int main() function
10         res.clear();
11         vector<int> path;
12         kk = k;
13         nn = n;
14         bc(0, path, 1);
15         
16         return res;
17     }
18     
19     void bc(int len, vector<int> path, int cur) {
20         if (len == kk) {
21             res.push_back(path);
22             return ;
23         }
24         
25         for (int i=cur; i<=nn; i++) {
26             path.push_back(i);
27             bc(len+1, path, i+1);
28             path.pop_back();
29         }
30         
31         return ;
32     }
33 };

View Code