力扣 39. 组合总和 递归解法

39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。
如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = ［１，３，６，７］
target = ７
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5]
target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = ［２］
target = 1
输出: []

题解：举例说明　i　为数组指针，ｘ　为此时指向元素　result　为结果

cur+[x]　表示所走过的所有数字

元素可以重复利用，则每次遍历一个元素，并求出此时的余数作为新的目标值，
      如果余数（新目标）比这个数子大，则再次从这个元素开始遍历
      如果新目标等于这个数字则加入到结果列表
      否则跳出
           3 4 5 6 7 8 9 10   target=7
           
        i  x    new_target    result
        0  3      7-3=4           []
            （此时  3<4 则进入递归）
           3      4-3=1           []
             (3>1 跳出回到上一层，i指针移动）
          
        1  4        4           [3，4]
           （跳出回到上一层，i指针移动）
           
        2  5      7-5=2         [3，4]
           (5>2 跳出回到上一层，i指针移动）  
        3  6      7-6=1         [3，4]
           (6>1 跳出回到上一层，i指针移动） 
        4  7       target=7     [[3，4],[7]]
     此上步骤主要为演示递归过程，小于target才会进入递归，产生new_target，
     省略初始与target判断 即 recursive(0,target,[]) 这条代码

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 排序，便于后续判定，若后面的值大于target直接停止
        nums=sorted(candidates)
        self.res=[]
        # 定义递归函数
        """
        元素可以重复利用，则每次遍历一个元素，并求出此时的余数作为新的目标值，
        如果余数（新目标）比这个数子大，则再次从这个元素开始遍历
        如果新目标等于这个数字则加入到结果列表
        否则跳出

        """
        def recursive(j,new_target,cur):
            # 当指针移动，则重新开始，第一次进来的new_target就是target
            # 相当与先进行一次，单个值与target的判断
            for i in range(j,len(nums)):
                x=nums[i]
                if x <new_target:
                    recursive(i,(new_target-x),cur+[x])
                else:

                    if x ==new_target:
                        self.res.append(cur+[x])
                    break
        recursive(0,target,[])
        return self.res