卖萌的弱渣

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.

Example

For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]

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.

Solution

  • Time: O(n)
(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
28
29
30
31
32
33
34
35

class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def comb_helper(self,candidates,target,result,entry,sum):
        if sum > target:
            return
        if sum == target:
            tmp = []
            for j in entry:
                tmp.append(j)
            result.append(tmp)
            return
        for i in candidates:
            entry.append(i)
            self.comb_helper(candidates,target,result,entry,sum+i)
            entry.pop()
        return

    def combinationSum(self, candidates, target):
        # write your code here
        result = []
        entry = []
        if candidates == None:
            return result
        self.comb_helper(candidates,target,result,entry,0)

        # remove the duplicated answer
        ret = []
        for i in result:
            i = sorted(i)
            if i not in ret:
                ret.append(i)
        return ret