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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • 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;
}
}
}
上一篇:[JetBrains注册] 利用教育邮箱注册JetBrains产品(pycharm、idea等)的方法


下一篇:关于PYTHON_EGG_CACHE无权限的问题