0040. Combination Sum II.md

每日鸡汤：不要质疑你的付出，这些都会一种累积一种沉淀，它们会默默铺路，只为让你成为更优秀的人。

• 0040/ Combination Sum II
• 难度：Medium｜ 中等
• 相关知识点：Array| Backtracking
• 题目链接：https://leetcode.com/problems/combination-sum-ii/description/

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.



> 题解：https://leetcode.cn/problems/combination-sum-ii/solutions/2363941/40-zu-he-zong-he-iihui-su-qing-xi-tu-jie-7y8s/
 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]
 

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Solution1

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(start, target, ans):
            if target == 0:
                result.append(ans[:])
                return 

            for index in range(start, l):
                if index > start and candidates[index] == candidates[index -1]:
                    continue
                
                if target - candidates[index] < 0:
                    continue
                
                ans.append(candidates[index])
                backtracking(index+1 ,target - candidates[index] , ans)
                ans.pop()
                
        result = []
        l = len(candidates)
        candidates.sort()
        backtracking(0, target, [])
        return result
        

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        _sort = sorted(candidates)
        ans = []
        def backtest(_list, _sum, left):
            if left >= len(_sort): return 
            elif _sum + _sort[left] == target:
                ans.append(_list + [_sort[left]])
            elif _sum + _sort[left] < target:
                backtest(_list + [_sort[left]], _sum + _sort[left], left + 1)
                while left + 1 < len(_sort) and _sort[left] == _sort[left + 1]:
                    left += 1
                backtest(_list, _sum, left + 1)
                
                
        backtest([], 0, 0)
        return ans

复杂度分析 时间复杂度：O(2^n×n) ,其中 n是数组candidates 的长度 在递归时，每个位置可以选或不选， 空间复杂度：O(n)