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

思路：

典型的backtracking问题，用递归解比较简单易懂。这个方法在3sum那题中也有应用到。

扫描1:n的每个数i，对之后{i+1: n}的集合求k-1 combination问题。直到对某集合解0 combination问题时终止，并插入结果。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<vector<int> > combine(int n, int k) { vector<int> sol; vector<vector<int>> allSol; findComb(n, 1, k, sol, allSol); return allSol; } void findComb(int n, int start, int k, vector<int> &sol, vector<vector<int>> &allSol) { if(k==0) { allSol.push_back(sol); return; } for(int i=start; i<=n-k+1; i++) { sol.push_back(i); findComb(n, i+1, k-1, sol, allSol); sol.pop_back(); } } };