leetcode 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路：回溯

 1 class Solution {
 2 public:
 3     vector<vector<int>> combine(int n, int k) {
 4         vector<int> v;
 5         vector<vector<int> > res;
 6         combine(res, v, n, k, 0, 1);
 7         return res;
 8     }
 9     void combine(vector<vector<int> > &res, vector<int> &v, int n, int k, int cnt, int begin) {
10         if (cnt == k) {
11             res.push_back(v);
12             return ;
13         }
14         for (int i = begin; i <= n; ++i) {
15             v.push_back(i);
16             combine(res, v, n, k, cnt + 1, i + 1);
17             v.pop_back();
18         }
19     }
20 };