LeetCode #39 Combination Sum

Posted on | Post modified | In , , , , , , , ,

Problem

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.

Examples

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

Boundary Conditions

Solution1

Method: Backtracking

Time Complexity:

Space Complexity:

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
27
28
29
30
31
32
33
34
class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def backtracking(answer, k, info):
            if k > 0 and answer[-1][1] == info[1]:
                ret.append([val for val, _ in answer])
            else:
                k += 1
                candidates = []
                
                if k == 1:
                    candidates = info[0]
                else:
                    pre_val = answer[-1][0]
                    if answer[-1][1] < info[1]:
                        candidates = [val for val in info[0] if val >= pre_val]

                for candidate in candidates:
                    if k == 1:
                        answer.append([candidate, candidate])
                    else:
                        val = answer[-1][1]
                        answer.append([candidate, val + candidate])
                    backtracking(answer, k, info)
                    answer.pop()
        
        ret = []
        backtracking([], 0, (candidates, target))
        
        return ret

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def combinationSum(self, candidates, target):
    res = []
    candidates.sort()
    self.dfs(candidates, target, 0, [], res)
    return res
    
def dfs(self, nums, target, index, path, res):
    if target < 0:
        return  # backtracking
    if target == 0:
        res.append(path)
        return 
    for i in xrange(index, len(nums)):
        self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

Solution2

Method: Dynamic Programming
Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        dp = [[[]]] + [[] for i in range(target)]
        for i in range(1, target + 1):
            for number in candidates:
                if number > i: break
                for L in dp[i - number]:
                    if not L or number >= L[-1]: dp[i] += L + [number],
        return dp[target]