40. 组合总和 II

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combination-sum-ii

题目

给定一个数组 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能应用一次。

阐明：

• 所有数字（包含指标数）都是正整数。
• 解集不能蕴含反复的组合。

示例 1:

输出: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]

示例 2:

输出: candidates = [2,5,2,1,2], target = 5,所求解集为:[  [1,2,2],  [5]]

解题思路

思路：回溯

这道题跟 39. 组合总和 相似，两者不同的中央在于：

• 【39. 组合总和】，candidates 中的数字能够无限度反复被选取；
• 【40. 组合总和 II】，candidates 中的每个数字在每个组合中只能应用一次。

这里还有个隐式的条件就是，这道题中没有强调给定数组元素重复性问题，而在示例中，咱们也能够看到元素在数组中是存在反复的状况，这也是一个不同点。

两者雷同的中央在于：

• 解集中不能蕴含反复的组合，也就是雷同数字不同排序视为反复。

在第 39 题中，因为元素不反复且可屡次选取同个元素，所以采取的策略中只有防止不产生反复组合即可。

在第 40 题，也就是本题当中，咱们次要须要解决的就是数组元素存在反复状况的问题，上面是解决的方法：

• 首先先将数组进行排序，这样反复的元素地位相邻，能够疾速去重；
• 因为不容许组合反复（雷同数字不同排序视为反复），所以递归每层不能存在反复的元素。
• 为了防止反复抉择同个元素，进入上层递归时，抉择下一个索引地位对应的元素。

这里用一个简略图示来加深了解，如下：

这里同样只选取其中一个分支绘制图示，因为其余分支同样是采纳雷同的策略。若不了解，同样可自行补全并加深了解。

依照这样的思路进行书写代码，具体如下。

class Solution:    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:        # 将数组进行升序排序        candidates.sort()        # 后果列表        ans = []        # 可能组合        tmp = []                def helper(idx, total):            if total == target:                ans.append(tmp[::])                return            if total > target:                return            for i in range(idx, len(candidates)):                # 这里限度同一层不能抉择值雷同的元素                # 若有雷同的元素，优先选择索引靠前的                if candidates[i-1] == candidates[i] and i-1 >= idx:                    continue                                total += candidates[i]                tmp.append(candidates[i])                # 这里留神，与 39 题不同，进入递归下一层                # 从以后索引的下一位开始选取，防止反复选取同个元素                helper(i+1, total)                # 回溯                tmp.pop()                total -= candidates[i]                    total = 0        helper(0, total)        return ans

这里将 39. 组合总和 的题解放在这里，能够联合本题加深了解。

欢送关注

公众号 【书所集录】