39. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
本题要从一个集合中取出一些数，使得和为某个特定的数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。
二刷。没必要排序，直接DFS选当前及后续元素即可，代码如下：
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
if (target == 0) {
ans.push_back(cur);
return;
}
if (target < 0)return;
for (int i = idx; i < candidates.size(); ++i) {
target -= candidates[i];
cur.push_back(candidates[i]);
dfs(candidates, target, ans, cur, i);
cur.pop_back();
target += candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
dfs(candidates, target, ans, cur, 0);
return ans;
}
};
本代码提交AC，用时12MS。