40. Combination Sum II.md

40. Combination Sum II (medium)

[tag] DFS, combination

• don't forgot to use early termination for DFS.

'''
1 1 2 5 6 10
1
1 1'
1 2
index = 0 1'
index = 1
'''
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        temp = []
        ans = []
        # cur_sum = 0
        def dfs(index, cur_sum):
            if cur_sum > target:
                return
            if cur_sum == target:
                ans.append(temp.copy())
                return
            for i in range(index, len(candidates)):
                if i > index and candidates[i] == candidates[i-1]:
                    continue
                temp.append(candidates[i])
                dfs(i + 1, cur_sum + candidates[i])
                temp.pop()
        dfs(0, 0)
        return ans