Combination Sum

Question

Given a set of candidate numbers (C) 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.

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.

Thoughts

Like permutation

but the number can be used more than once

注意点 object is mutable, so everytime find a copy you need to create a copy of the current list stackoverflow explain

Solution

class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        # write your code here
        if not candidates or not target:
            return []
        self.resultList = []
        #remember to sort the list to keep ascending order
        candidates.sort()
        self.candidates = candidates
        self.helper([], 0, target)
        return self.resultList

    def helper(self, curSet, index, target):                                                                                              
        if target == 0:
            #need to create a copy of the result
            result = curSet[:]
            self.resultList.append(result)
        for i in range(index, len(self.candidates)):
            if self.candidates[i] > target:
                break
            else:
                curSet.append(self.candidates[i])
                #can use number repeatly, but ascending order
                self.helper(curSet, i, target - self.candidates[i])
                curSet.pop()

if __name__ == "__main__":
    list = [2, 3, 6, 7]
    target = 7
    so = Solution()
    result = so.combinationSum(list, target)
    print result