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~n的所有k组合数，和求排列数有点类似。当然也是递归的思路，每个数都有取和不取两种情况，分别递归。唯一需要注意的是递归遍历的时候不走回头路，这样才不会重复。比如求1,2,3,4的两数组合，第一个取1，第二个可以取2,3,4；当第一个取2时，就不再回过头来测试1了，因为之前测试1时，已经产生了{1,2}这个组合，现在测试2时，只需要往前测试3,4了。 完整代码如下：

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidate, int step, int& n, int& k)
    {
        if (candidate.size() == k) {
            ans.push_back(candidate);
        }
        else {
            for (int i = step; i <= n; i++) { // 从第step步开始
                candidate.push_back(i);
                work(ans, candidate, i + 1, n, k); // 下一步从i+1步开始
                candidate.pop_back();
            }
        }
    }
    vector<vector<int> > combine(int n, int k)
    {
        vector<vector<int> > ans;
        vector<int> cand;
        work(ans, cand, 1, n, k);
        return ans;
    }
};

本代码提交AC，用时113MS。

二刷。还有一种解法，对于每个数，有两种选择，要么拿要么不拿，代码如下：

class Solution {
public:
	void dfs(vector<vector<int>> &ans, vector<int> &cand, int n, int k) {
		
		if (cand.size() == k) {
			ans.push_back(cand);
			return;
		}
		if (n == 0)return;

		cand.push_back(n);
		dfs(ans, cand, n - 1, k);
		cand.pop_back();

		dfs(ans, cand, n - 1, k);
	}
	vector<vector<int>> combine(int n, int k) {
		vector<int> cand;
		vector<vector<int>> ans;
		dfs(ans, cand, n, k);
		return ans;
	}
};

本代码提交AC，用时148MS。