Combination Sum I, II

LeetCode 39, 40

I

class Solution:
    def combinationSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        self.res = []
        self.dfs(nums, target, [], 0)
        return self.res
        
    def dfs(self, nums, target, path, index):
        if target ==0:
            self.res.append(path)
        if target < 0:
            return
        # 當圖往下畫時, 你就會有感覺需要用 for loop
        for i in range (index, len(nums)):
            self.dfs(nums, target - nums[i], path+[nums[i]], i)
            # 這會迴傳 [[2,2,3],[7]]
            # 
            # self.dfs(nums, target - nums[i], path+[nums[i]], index)
            # 底下會迴傳[[2,2,3],[2,3,2],[3,2,2],[7]]

II

The solution set must not contain duplicate combinations

class Solution:
    def combinationSum2(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        self.res = []
        nums.sort()
        self.dfs(nums,target, [], 0)
        return self.res
        
    def dfs(self, nums, target, path, index):
        if target ==0:
        # 選擇1. 判斷式可以加在這 if path not in self.res:
            self.res.append(path)
            return
        if target < 0:
            return
        
        for i in range (index, len(nums)):
        #選擇2. 判斷 i 在起點之後是否有與目前重複的值(i > index), 有代表會被重複選到
            if i > index and nums[i] == nums[i - 1]:
                continue
            if nums[i] > target:
                break
            self.dfs(nums, target - nums[i], path+[nums[i]], i+1)