135. 数字组合

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum(self, candidates, target):
        # write your code here
        #for循环里面内嵌dfs写法 + 排序 + 去重
        
        results = []
        candidates.sort()
        #递归的调用
        self.dfs(results, [], 0, candidates, target)
        return results
        
    
    #递归的定义
    #传入参数
    def dfs(self, results, array, curindex, candidates, remaintarget):
        #递归的出口，如果remaintarget小于0的时候，返回，继续下一次的寻找
        if (remaintarget < 0):
            return
        
        #如果符合条件，remaintarget == 0,则加进results里面
        if (remaintarget == 0):
            #注意：如果是append(array)是浅拷贝，只拷贝指针，不拷贝数据，array改变，上一个array指向的也是同样内存地址。list或者arrar[:]是深拷贝，拷贝指针也会拷贝数据进来
            results.append(list(array))
            return results
            
        #递归的拆解,for循环里面内嵌dfs写法
        for i in range(curindex, len(candidates)):
            #去重处理,如果当前索引不同，但是值相同，则说明是重复的
            if (i != 0) and (candidates[i] == candidates[i - 1]):
                continue
            
            array.append(candidates[i])
            #不停的dfs，直到remaintarget==0或者< 0的时候返回
            self.dfs(results, array, i, candidates, remaintarget - candidates[i])
            #如果返回了，则开始往回移除值，一个一个移除在进行判断是否符合
            array.pop()