Monday, November 17, 2014

[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();
        } 
    }    
};

3 comments: