LeetCode Combination Sum

LeetCode Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

本题要从一个集合中取出一些数,使得和为某个特定的数target,输出所有的这种组合。注意不能有重复的组合,比如[2,2,3]和[3,2,2]算是重复的。

这是很常见的组合问题,使用递归的思路求解。比如样例,要求和为7,则每个加数必须小于等于7,所以依次尝试2,3,6,7,如果是2,则还差7-2=5,所以递归的在[2,3,6,7]里面找和为5的组合。如此递归,直到差为0。但是这样有一个问题,比如你这一次尝试的是2,则可能得到[2,2,3]的组合,下一次尝试3,则可能得到[3,2,2]的组合,但是这两个组合是相同的。我一开始的想法是对组合排序,然后用set去重。代码如下:

class Solution {
public:
	void work(set<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			vector<int> tmp = sol;
			sort(tmp.begin(), tmp.end());
			ans.insert(tmp);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		set<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return vector<vector<int>>(ans.begin(), ans.end());
	}
};

本代码提交AC,但是用时145MS,只击败了4.5%的人,所以肯定还有更优的方案。

上述方案的一个费时的地方就是要对每个组合排序,然后用set去重,如果能省掉这个环节,速度会快很多。

网上查看题解之后,恍然大悟,每次只选不小于上一次选过的数,这样得到的组合就不会有重复,不需要排序,也不需要set去重。比如上面的例子,在选到3时,差7-3=4,此时再从[2,3,6,7]里面选时,只选大于等于3的数,也就是3,6,7,不再考虑2了。但是6,7都大于4,不行;3的话,剩余4-3=1也无解。所以搜3的时候,就不会得到[3,2,2]的结果,也就无需去重。

完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() - 1]))continue;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return ans;
	}
};

本代码提交AC,用时20MS,速度快了好多。

后来我发现这个版本的代码还可以优化,因为candidates已经排好序了,如果这次取了i号元素,下一次只要取i及以后的元素即可,所以在递归的时候多传入一个下标值,也能提速。完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, i, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

本代码提交AC,用时16MS。

2 thoughts on “LeetCode Combination Sum

  1. Pingback: LeetCode Combination Sum II | bitJoy > code

  2. Pingback: LeetCode Combination Sum IV | bitJoy > code

Leave a Reply

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