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

Diffculty
Medium

Similar Problems
[LeetCode ] Combination Sum Medium [LeetCode ] Permutations Medium

Analysis

思路： 排列组合这一类的题目都是采用深度优先搜索策略，通过递归回溯的算法去处理。 跟排列不同的是，这里需要用一个临时变量来记录已经选择了几个数字，因为组合是从一个集合种选择几个固定的数。 比如，要选择 k 个数，我们用 cur 变量来记录递归当当前层的时候已经选择的元素的数量，每递归一层，cur 都加 1。

一、经典的递归写法

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> sol;
        vector<int> path;
        combine(n, k, 1, 0, path, sol); // 1, 2, 3, 4
        return sol;
    }

private:
    // start，开始的数, cur，已经选择的数目
    static void combine(int n, int k, int start, int cur, vector<int> &path, vector<vector<int> > &sol){
        if (cur == k) {                // 可以用 sol.size() == k 或者 sol.size() == k 代替
            sol.push_back(path);
            return;
        }

        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            combine(n, k, i + 1, cur + 1, path, sol);  // 注意跟排列的区别，这里是 i + 1，而不是 start + 1
            path.pop_back();
        }
    }
};

// 代码二： class Solution { public: vector > combine(int n, int k) { vector> result; if(n < k || k <= 0) return result; return combine_helper(1, n, k); }

private: vector> combine_helper(int start, int end, int k){ vector> result;

if(k == 1){
  for(int i = start; i <= end; i++){
    vector<int> temp;
    temp.push_back(i);
    result.push_back(temp);
  }
  return result;
}

for(int i = start; i <= end - k + 1; i++){
  vector<vector<int>> temp;
  temp = combine_helper(i + 1, end, k - 1);
  for(int j = 0; j < temp.size(); j++){
    temp[j].insert(temp[j].begin(), i);
    result.push_back(temp[j]);   
  }
}

return result;

} };