Combination Sum
:https://leetcode.com/problems/combination-sum
这道题目由于数据量比较大，所以好的方法和差的方法时间上来说，差非常的多。
这道题目的主要要求就是：给定一个数组，和一个数T，要求用数组里面的数进行组合，使组合出来的数的和为数T，数组里面的数可以重复使用。
如：[2,3,6,7]和数7，
给出的解应该是:[7],[2,2,3]
刚开始的时候，想法比较简单，就是简单的把数组遍历过去，用或者不用这个数，然后进行下一步，采用递归的方法，最后整个递归的终止条件就是和变为0，此时把结果输入，否则，丢弃结果。
//code1
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> sets;
sort(candidates.begin(), candidates.end());
Iter(ret,candidates, target, sets, 0, candidates.size()-1);
return ret;
}
void Iter(vector<vector<int>>& ret, vector<int> candidates, int target, vector<int> sets , int startIndex, int end)
{
if(target==0){
ret.push_back(sets);
return;
}
if(startIndex > end || target < 0)
return;
Iter(ret, candidates, target, sets, startIndex+1,end);
sets.push_back(candidates[startIndex]);
Iter(ret,candidates, target-candidates[startIndex], sets, startIndex,end);
return;
}
};
这个代码比较简单，提交之后也AC了，但是发现时间竟然用了300ms。基本已经属于最差的方法了。这个，分析能力比较弱，自己分析不出来到底时间复杂度是多少……自己这方面比较薄弱，找机会好好补补。
这个方法肯定不行，需要改进。首先想到的是，能不能把vector数据变成引用的，这个时间应该会有所优化。
看了一下，sets没办法直接改，但是candidates可以，后来把candidates的数据变成引用传参数，时间竟然一下子变成了190ms。
就一个引用改了一下，直接快了1/3……
下面就要想办法，把sets也使用引用的方法，来改进。
看了一下提示，用回溯的方法。
通过提示，本着用引用的方法，进一步优化：
//code2
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int end = candidates.size() - 1;
vector<vector<int>> ret;
vector<int> sets;
sort(candidates.begin(),candidates.end());
Iter(ret,candidates,sets,target,0,end);
return ret;
}
void Iter(vector<vector<int>>& ret,vector<int>& candidates,vector<int> sets, int target, int index, int end)
{
if(index > end)
return;
if(target < 0)
return;
if (target == 0){
ret.push_back(sets);
return;
}
sets.push_back(candidates[index]);
Iter(ret, candidates, sets, target-candidates[index], index, end);
sets.pop_back();
Iter(ret,candidates,sets,target, index+1,end);
return;
}
};
这个方法的时间是28ms.比最开始的代码整整快了将近10倍。
仔细看上下两个代码，可以看出，一开始的代码(code1)是先用当前的sets去进行下一次的递归，表示当前的startIndex不使用，然后在考虑当前的stratIndex被加上的过程。具体的代码如下：
Iter(ret, candidates, target, sets, startIndex+1);
sets.push_back(candidates[startIndex]);
Iter(ret,candidates, target-candidates[startIndex], sets, startIndex);
而后来的28ms的代码（code2），刚好和上面的反了一下，是先加上当前的index里面的值，递归，然后pop出当前的值，再次递归。
sets.push_back(candidates[index]);
Iter(ret, candidates, sets, target-candidates[index], index, end);
sets.pop_back();
Iter(ret,candidates,sets,target, index+1,end);
两者在本质上来说是没有区别的，为了比较，把28ms的方法的sets改为非引用参数，最后得到的结果是196ms。也就是说，两个code在方法上面，时间复杂性其实是一样的。两者之所以有这么大的时间差别是因为参数的引用和非引用。对于非引用参数来说，每次的函数调用都要用到拷贝函数，而引用实际上是通过指针做到得，所以时间上，两者差距会这么大。
所以，现在考虑把code1的sets变量变为引用变量，会出现Output Limit Exceeded的问题。
这个主要是因为，如果使用引用，code1没有pop的过程，所以sets会一直增加元素，最后会导致在sets里面的元素越来越多。而code2，是采用了回溯的思想，有pop元素的过程，从整体上面来看，始终是先push一个元素，然后pop一个元素，整个sets在最后相当于没有变，还是原来的sets，并不会随着递归层数的增加，而无尽的增加sets的元素。所以可以使用引用参数。
后来看了一下时间分布图，发现28ms还是不够，还有比它快的。
看了一下discuss，发现，类似剪枝，由于candidates是按顺序排列的，所以当target小于当前的candidates[index]时，后面就不用再进行下去了，肯定不可能有解得所以加一句：
if(target
< candidates[index])
return;
得到的时间是16ms，基本是比较快的时间了
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int end = candidates.size() - 1;
vector<vector<int>> ret;
vector<int> sets;
sort(candidates.begin(),candidates.end());
Iter(ret,candidates,sets,target,0,end);
return ret;
}
void Iter(vector<vector<int>>& ret,vector<int>& candidates,vector<int>& sets, int target, int index, int end)
{
if(index > end)
return;
if(target < 0)
return;
if (target == 0){
ret.push_back(sets);
return;
}
if(target < candidates[index])
return;
sets.push_back(candidates[index]);
Iter(ret, candidates, sets, target-candidates[index], index, end);
sets.pop_back();
Iter(ret,candidates,sets,target, index+1,end);
return;
}
};
总结：从上面的分析可以看到，以后对于vector等”数据类“，尽量用引用参数来进行参数的传递。实际上，最开始的300ms和28ms的两个算法在本质上是没有分别的，两者的时间复杂度应该是一样的。但是在具体的时间差距上，就相差比较大了。主要就是因为一些小细节的差别。所以这点就说明，单纯的用时间复杂度来刻画一个算法的快慢，也是有一定的局限性的，因为时间复杂性毕竟是在n趋向于无穷大的时候的复杂度，我们往往忽略了那个常数，但是当n不是那么大的时候，那个常数的作用还是比较大的。当然，这道题的时间差距和那个常数无关，主要是一些细节的方面导致的时间差距。但是从另一个方面来说，这个应该也可以归因到时间复杂度的常数范畴里。
版权声明：本文为博主原创文章，未经博主允许不得转载。