comnination_sum.py

class Solution(object):
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        temp = []
        candidates = sorted(candidates)
        self.backtracking(candidates, res, temp, target, 0)
        return res
    def backtracking(self, candidates, res, temp, remain, start):
        if remain < 0 : return
        if remain == 0: res.append(temp[:])
        for i in range(start, len(candidates)):
            temp.append(candidates[i])
            self.backtracking(candidates, res, temp, remain - candidates[i], i)
            temp.pop()