Leetcode2 组合总和、组合总和II、组合

今天了做了三道比较常规的递归+组合问题

组合总和：

数组中不存在重复元素，但是一个元素可以重复多次选择。就像实例1中的 2 2 3一样。

所以这道题的思路就是：

1. 控制递归的时候从左向右遍历数组

2. 因为可以选择重复的数字，所以在下次递归的时候还可以从当前下标尝试一次

3. 如果当前值已经超出了预期结果，直接return，说明这种尝试失败了。

   具体的代码如下：

组合总和II：

在数组中存在重复的数字，最后的结果中不能包括重复的策略。因此这道题有点像全排列II，在上面的代码基础上，我们将数组按照升序或者是降序进行排列，还是需要保证从左向右进行扫描。如果当前遍历到的下标对应的数字和前面一个相同，并且前面一个数字不在当前的递归树上，我们就可以继续递归。在不在当前的递归树上，我们还是可以采用全排列II中的方法记录。这里举个例子：

在我们排序之后，我们会从左往右遍历数组，不会试探重复的元素。因为我们在退出递归的时候会恢复现场，所以在情况二中vis[j-1] = false，表明这种情况及其后续分值已经被完成了，所以如果nums[j] == nums[j-1] 直接跳出。

这里我感觉在上篇文章中没有解释清楚，如果看到的小伙伴还是存在疑问的话可以私信我交流一下~

具体的代码如下所示：

组合

使用递归的话有明显的几处可以进行剪枝：

因为生产的数组不能存在重复值，所以我们还是从左往右进行扫描，然后扫描之后其实我们是在剩余的元素组成的数组中进行挑选。考虑一种最坏的情况，剩余元素假设被选择完，可以构成K个数吗？ 所以当前选择数字的个数和剩余数组的元素还有K三者存在一个关系，我们通过这个关系可以进行剪枝：

具体代码如下：