力扣-40-组合总和Ⅱ

复习下原题，之前做过的，4个月前了

第一眼看到觉得是完全背包，但是好像不太一样
然后想到了回溯

我很快写了一个标准的回溯出来，但是意识到好像不太对

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		backTrack(candidates, target);
		return res;
	}

	void backTrack(vector<int>& nums,int target) {
		if (target < 0) return;
		if (target == 0) {
			res.push_back(temp);
			return;
		}
		for (int i : nums) {
			temp.push_back(i);
			backTrack(nums,target-i);
			temp.pop_back();
		}
	}
};

它跟排列和组合都不一样，它可以重复选，但是最终的结果会被认为是重复的同一结果，直观来说就是这样：

2 2 3
2 3 2
3 2 2
7

前三个我们认为是同一个，我现在要做的就是去重
稍微还有点映像，是每次只有比上一个数字大才插进去
即如果每次选择的元素大于上一个元素，这样可以保证得到唯一的递增组合
想到的最简单的实现就是加一个递归参数判断

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		backTrack(candidates, target,0);
		return res;
	}

	void backTrack(vector<int>& nums,int target,int pre) {
		if (target < 0) return;
		if (target == 0) {
			res.push_back(temp);
			return;
		}
		for (int i : nums) {
			if (i < pre) continue;
			temp.push_back(i);
			backTrack(nums,target-i,i);
			temp.pop_back();
		}
	}
};

回溯+单增去重，可能是最直接的实现了

正文

然后才是看今天的题目，基本上没差，就只是不能重复使用了
有点像是去重后的排列的感觉
之前排列标记已选过的元素用的是交换的方式，通过一个标记index来标记当前排到了多少位并于当前选中元素的位置交换

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		backTrack(candidates, target,0,0);
		return res;
	}

	void backTrack(vector<int>& nums,int target,int index,int pre) {
		if (target < 0) return;
		if (target == 0) {
			res.push_back(temp);
			return;
		}
		for (int i = index; i < nums.size(); i++) {
			if (nums[i] < pre) continue;
			temp.push_back(nums[i]);
			swap(nums[index], nums[i]);
			// 注意这里要减去的目标位置被交换了，所以不是num[i]而是nums[index]
			backTrack(nums, target - nums[index], index + 1,nums[index]);
			swap(nums[index], nums[i]);
			temp.pop_back();
		}
	}
};

我照着前面的思路写出来，但是结果是这样的

1 2 5
1 7
1 1 6
2 6
1 1 6
1 2 5
1 7

我意识到不是我之前的做法有问题，而是这里题目不一样了，题目数组中是有相同元素的

输入: candidates = [10,1,2,7,6,1,5], target = 8,

嗯，题目不允许重复选择，结果也不允许重复，但是又有相同元素

应该说是同一轮选择中不能选中重复的相同元素，但是怎么做到呢？

关键是在for (int i = index; i < nums.size(); i++) {这里跳过重复的元素

啊，我突然意识到了评论1的巧妙
排序一次的话，就完全就不需要我做的两步操作（同组递增，和交换位置防止重选，这样也没法解决上面的问题）
如果是排序后的数组中选择的话，就只需要像组合一样，选后面的就完事了，1来绝对不会选重，2来保证了所有的结果递增（排列唯一），3来还能方便对每一层for去重

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		sort(candidates.begin(), candidates.end());
		backTrack(candidates, target, 0);
		return res;
	}

	void backTrack(vector<int>& nums, int target, int index) {
		if (target < 0) return;
		if (target == 0) {
			res.push_back(temp);
			return;
		}
		for (int i = index; i < nums.size(); i++) {
			if (i > index && nums[i] == nums[i - 1]) continue;
			temp.push_back(nums[i]);
			backTrack(nums, target - nums[i], i + 1);
			temp.pop_back();
		}
	}
};

所以总结一下，

1. 和排列的区别：
   这里的一次排序肯定是有额外的时间复杂度的，主要是这一趟排序能巧妙地解决三个问题，如果是像排序那样（1不能重复选，2接收排列不同看作是不同的结果，3没有重复数字），不使用一趟排序而是用交换可能效率更高

2. 和原题的区别：1原题无限制取本题只能用一次，2原题不包含重复元素本题包含
   相同点是对于不同的排列看作是相同的结果