LeetCode40——Combination Sum II

浅浅的花香味﹌ 2022-08-09 09:39 115阅读 0赞

与上一题[Combination Sum][]类似，只不过是有放回的取。

这题最关键的就是去重。所谓去重，不是删除序列中重复的元素，而是当序列中出现相同的数时，会递归产生相同的结果。

例如：序列排序后为

1 1 2 3 4

假如target为3，不去重的话就会产生两个\[1,2\]，分别由索引为0和索引为1的1和2组合产生。

在代码中提出了先获取result再对result进行去重的操作，这种办法是超时的。

去重操作在深度搜索中就进行：

定义当前搜索的开始索引，如果当前深度的值（nums\[i\]）与上一深度的值(nums\[i-1\])相等则continue;

当然还得满足一个大前提，当前深度非起始深度，这样就保证了如下情况的结果：

例如：序列排序后是为

1 1 2 3 4

target为5

则结果集中会有\[1,1,3\]

代码：

class Solution {
    private:
    	void myFun(int sum,int target,int start,vector<vector<int>>&result,vector<int>temp,vector<int>candidates)
    	{
    		if (sum == target)
    		{
    			result.push_back(temp);
    			return;
    		}
    		if (sum > target)
    			return;
    		for (int i = start;i<candidates.size();i++)
    		{
    			if (i!=start&&candidates[i] == candidates[i - 1])//去重
    					continue;
    			temp.push_back(candidates[i]);
    			myFun(sum + candidates[i], target,i+1 ,result,temp,candidates );
    			temp.pop_back();
    		}
    	}
    public:
    	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    		sort(candidates.begin(), candidates.end());
    		//candidates.erase(unique(candidates.begin(),candidates.end()),candidates.end());
    		vector<vector<int>>result;
    		vector<int>temp;
    		myFun(0, target, 0, result, temp, candidates);
    		//超时
    		//sort(result.begin(),result.end());
    		//result.erase(unique(result.begin(),result.end()),result.end());
    		return result;
    	}
    };

[Combination Sum]: http://blog.csdn.net/zhangxiao93/article/details/49207467