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. 组合总和 的题解放在这里，能够联合本题加深了解。

欢送关注

公众号【书所集录】