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 toT.

Thes ame 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 target7, A solution set is:

[
  [7],
  [2, 2, 3]
]

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

        retList = []
        if not candidates:
            return []
        if not target:
            return []

        self.combinationSumHelper(candidates, target, retList, [], 0)
        return retList

    def combinationSumHelper(self, candidates, target, retList, curList, start):

        #res = 0
        #print 'curList: ', curList, ' target: ', target
        if target < 0:
            return

        if target == 0:
            # Note: remember to copy over the curList using the [:] slicing technique for lists
            retList += [curList[:]]
            #print 'retList: ', retList
            return

        for idx in xrange(start, len(candidates)):
            elem = candidates[idx]
            # Note: Two ways of doing, either make a new list or if the same list is used then do a pop()
            #       after it returns

            #newList = curList + [elem]
            #print 'newList: ', newList
            #self.combinationSumHelper(candidates, (target - elem), retList, newList, idx)

            curList += [elem]
            self.combinationSumHelper(candidates, (target - elem), retList, curList, idx)
            curList.pop()