卖萌的弱渣

I am stupid, I am hungry.

Combination Sum

Given a set of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

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

Note

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

Example

given candidate set 2,3,6,7 and target 7,

A solution set is:

1
2

[7] 
[2, 2, 3]

Solution

  • DFS
(Combination-Sum.py) download
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

class Solution(object):
    def recur_helper(self,c,target,result,vector,cur):
        if target == 0:
            result.append(vector[:])
            return

        while cur<len(c):
            if c[cur] <= target:
                vector.append(c[cur])
                self.recur_helper(c,target-c[cur],result,vector,cur)
                vector.pop()
            cur += 1
        return

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        result = []
        candidates = sorted(candidates)
        if candidates == None or len(candidates) == 0:
            return result
        self.recur_helper(candidates,target,result,[],0)
        return result