[LeetCode] Challenge log 40

Posted on |
40. Combination Sum II

Analysis: Similar to 39. Make sure to not to call dfs with same number at one level.

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

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

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(candidates)
        if n == 0: return []
        
        res = []
        nums = sorted(candidates)
        
        def dfs(target, st, index):
            if target == 0: 
                res.append(st)
                return
            for i in range(index, n):                
                # triming
                if i > index and nums[i] == nums[i-1]: continue
                if nums[i] > target: break
                # dfs
                dfs(target - nums[i], st + [nums[i]], i + 1)
        
        dfs(target, [], 0)
        return res
0%