正文
leetcode第38题--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.
- Elements in a combination ( a 1, a 2, … , a k) must be in non-descending order. (ie, a 1 ≤ a 2 ≤ … ≤ a k).
- 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]
题目的意思是给定一个candidate集合，里面包含一些数字，给定一个目标T，在集合中找出可以组合成T的所有组合，集合中的数字可以重复利用。但组合后的结果不能重复。结果中按非降序排列。举例集合C为 2,3,6,7 目标位7，那么就有两种组合满足，一个是[2，2， 3] 一个是[7]
思路：
利用回溯法，深度优先。剪枝判断是相加的数大于目标时返回，或者相加之和为目标的时候记录在ans中并返回。如果相加小于目标，那就往下一层找，找到满足要返回的条件为止。
class Solution {
public:
int sum38(vector<int> vec) // 返回vec中所有值的和，用来和target判断用
{
if (vec.size() == 0)
return -1;
int len = vec.size(), ans = 0;
for (int i = 0; i < len; ++i)
{
ans += vec[i];
}
return ans;
}
void back38(vector<vector<int> > &ans, vector<int> &candidates, vector<int> &tmp, int target, int cur)
{
for (int i = cur; i < candidates.size(); ++i) // i从传入的cur下标开始，cur初始为0，之后根据i改变，为了保证不会有重复解
{
int num = sum38(tmp); // 避免三个if语句都调用sum38，计算一次就好,否则超时
if (num == target)
{
ans.push_back(tmp); // 如果找到了一组，就记录后返回
return;
}
if (num < target) // 如果比目标还小，说明还要在加一个数
{
tmp.push_back(candidates[i]);
back38(ans, candidates, tmp, target, i); // tmp加了一个数后再递归，注意此处传入的cur为i，这样为了保证不会有重复的解
// 因为candidates是排好序的，所以之后递归中要加的数只能是下标i之后的
tmp.pop_back(); // 递归返回到这可定是之前相等或者是大于了，所以要去掉tmp的最后一个，再继续找
}
if (num > target)
{
return;
}
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target)
{
std::sort(candidates.begin(), candidates.end()); // 因为给的数不是有序的，所以一定要先排好序，才能为之后避免重复解
vector<vector<int> > ans;
vector<int> tmp;
back38(ans, candidates, tmp, target, 0);
return ans;
}
};
这个在oj上要440ms。发现时间主要是用在计算vec的和上了。在网上看别人的做法，发现还有个巧妙的技巧。就是传入的target每次变小，知道为零是即为满足条件。剪枝判断是用target和当前想要加入的元素进行比较，如果target比较大那就把target减去要加入的元素之后的值当做下一次的target。同理如果要加入的值都比当前的target更大了就可以剪枝返回了。
这个代码只要80ms，提高了5倍
void back38(vector<vector<int> > &ans, vector<int> &candidates, vector<int> &tmp, int target, int cur)
{
for (int i = cur; i < candidates.size(); ++i)
{
if (0 == target) // 为零即之前的组合满足最初target
{
ans.push_back(tmp);
return;
}
if (candidates[i] <= target) // 如果将要加入的不比目标大，加入
{
tmp.push_back(candidates[i]);
back38(ans, candidates, tmp, target - candidates[i], i);
tmp.pop_back();
}
if (candidates[i] > target) // 剪枝
{
return;
}
}
}
