LeetCode Combinations

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

求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。

One thought on “LeetCode Combinations

  1. Pingback: LeetCode Subsets | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *