39.md

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) 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.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

my thoughts:

1. backtracking.

my solution:

**********175 ms
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        candidates.sort()
        res = []
        cur = []
        self.helper(candidates, target, cur, res, 0)
        return res
    
    def helper(self, cans, target, cur, res, idx):
        #print cur, target
        if target == 0:
            res.append(cur)
            #print res
            return
        if target < 0:
            return
        for i in range(idx, len(cans)):
            #cur.append(cans[i])
            self.helper(cans, target-cans[i], cur+[cans[i]], res, i)
            #cur.pop()

my comments:

it is kind of confusing why using cur.append + cur.pop will give wrong answer.
* seems I need to list() the cur before add to res. the list() makes a deep copy of cur.

from other ppl's solution:

1. need to look more, 82ms:
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates = sorted(candidates)
        
        def track(cands,start, target, currlist,solset):
            if target == 0:
                solset.append(list(currlist))
            if start>=len(cands) or target<cands[start]:
                return
            track(cands, start+1, target, currlist, solset)
            currlist.append(cands[start])
            track(cands, start, target-cands[start], currlist, solset)
            currlist.pop()
        
        solset =[]
        track(candidates,0,target,[], solset)
        return solset