Leetcode题40、组合总和II（Python题解）

问题：

题目来源：力扣（LeetCode）

leetcode40.组合总和II

难度：中等

分析： 回溯法。 题目中有重复元素，需要进行去重。首先元素需要排序，然后每次遇到重复的值即跳过，并且保证备选数组的第一个值永远是可选的，i > index。

解决方法： 1：回溯法

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: if candidates == []: return [[]] def backtrack(index): if sum(path) == target: res.append(path[:]) for i in range(index, len(candidates)): if i > index and candidates[i] == candidates[i - 1]: continue path.append(candidates[i]) if sum(path) <= target: backtrack(i + 1) path.pop() path = [] res = [] candidates.sort() backtrack(0) return res