[LeetCode] Challenge log 39

Posted on |
39. Combination Sum

Analysis: DFS problem + Triming

Triming Strategy:

  1. sort the array in accending order
  2. when looping through the array, if current number > target, break
  3. when looping through the array, start from the last (greatest number) in the stack

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

The same repeated number may be chosen from candidates unlimited number of times.

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
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(candidates)
        if n == 0: return [] 
        
        def recur(target, st):
            if target == 0: res.append(st)
            for num in nums:
                if num > target: break
                if st and num < st[-1]: continue
                recur(target - num, st + [num])

        res = []       
        nums = sorted(candidates)
        recur(target, [])
        return res
0%