组合总和

https://leetcode-cn.com/problems/combination-sum/

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        if candidates is None or len(candidates) == 0:
            return result
        candidates.sort()
        path = []
        pos = 0
        self.helper(result,candidates,path,target,pos)
        return result
    def helper(self,result,candidates,path,target,pos):
        if target == 0:
            result.append(path[:])
        if target < 0 or pos >= len(candidates):
            return
        #避免出现[1,2,3],[3,2,1]的情况
        for i in range(pos,len(candidates)):
            path.append(candidates[i])
            # 可以出现[2,2,2,2],通过pos还可以选当前点本身来控制。
            self.helper(result,candidates,path,target-candidates[i],i)
            path.pop(-1)

组合总和 II

https://leetcode-cn.com/problems/combination-sum-ii/

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        if candidates is None or len(candidates) == 0:
            return result
        candidates.sort()
        path = []
        #定义一个记录是否访问过的数组
        visited = [0]*len(candidates)
        self.helper(result,candidates,path,target,0,visited)
        return result
    def helper(self,result,candidates,path,target,pos,visited):
        if target == 0:
            result.append(path[:])
        if target < 0 or pos >= len(candidates):
            return
        #避免出现[1,2,3],[3,2,1]的情况
        for i in range(pos,len(candidates)):
            #当跳过了一个元素去访问下一个相同的元素时，就会出现重复
            if i != 0 and candidates[i] == candidates[i-1] and visited[i-1] == 0:
                continue
            visited[i] = 1
            path.append(candidates[i])
            # 可以出现[2,2,2,2],通过pos还可以选当前点本身来控制。
            self.helper(result,candidates,path,target-candidates[i],i+1,visited)
            path.pop(-1)
            visited[i] = 0

组合问题3
https://leetcode-cn.com/problems/combination-sum-iii/

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        nums = [1,2,3,4,5,6,7,8,9]
        results = []
        path = []
        self.helper(results,nums,path,k,n,0)
        return results
    def helper(self,results,nums,path,k,n,pos):
        if len(path) > k or (len(path) == k and n != 0):
            return 
        if n == 0 and len(path) == k:
            results.append(path[:])
        for i in range(pos,9):
            path.append(nums[i])
            self.helper(results,nums,path,k,n-nums[i],i+1)
            path.pop(-1)

组合求和4
https://leetcode-cn.com/problems/combination-sum-iv/
这个问题问的不是所有可能的组合而是组合的数量
用回溯就会超时，所以用了动态规划，动态规划统计方案数量

class Solution:
    def combinationSum4(self, nums, target):
        size = len(nums)
        if size == 0 or target <= 0:
            return 0

        dp = [0 for _ in range(target + 1)]
        
        # 这一步很关键，想想为什么 dp[0] 是 1
        # 因为 0 表示空集，空集和它"前面"的元素凑成一种解法，所以是 1
        # 这一步要加深体会
        
        dp[0] = 1

        for i in range(1, target + 1):
            for j in range(size):
                if i >= nums[j]:
                    dp[i] += dp[i - nums[j]]

        return dp[-1]