#leetcode簽到
Day 2

40. Combination Sum II

問題 : 怎麼組合可以sum==target (回傳數列不能有重複組合)

一開始寫了DP
發現不會全組合XD 後來改成用for append+pop(backtracking)
但是也沒有dedup
最後還是偷看人家的

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()

        def dp(i, now,target):


            if target == 0:
                res.append(now[:])
                return
            if target < 0:
                return

            for t in range(i, len(candidates)):
                if t > i and candidates[t] == candidates[t - 1]:
                    continue

                now.append(candidates[t])
                dp(t + 1, now, target - candidates[t])
                now.pop()

        dp(0,[],target)
        return res