> For the complete documentation index, see [llms.txt](https://zcjian.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zcjian.gitbook.io/project/array/combination-sum.md).

# Combination Sum I, II

LeetCode 39, 40

## I

```python
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]]
```

## &#x20;II

&#x20;The solution set must not contain duplicate combinations

```python
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)
```