回溯法解决组合问题

回溯法一般过程：

初始输出结果
result = []
if 满足当前状态接入结果中：
    result.append(当前状态)
for 选择 in 选择列表：
    做选择
    递归调用(traceback(选择列表， 当前列表))
    撤销选择

LeetCode 07.组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

class Solution:
    def combine(self, n, k):
        result = []
        def backtrack(start, subset):
            if len(subset) == k:
                result.append(subset[:])
                return
            for i in range(start, n+1):
                subset.append(i)
                backtrack(i+1, subset)
                subset.pop()
        backtrack(1, [])
        return result          

S = Solution()
S.combine(4,2)

LeetCode 39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        def backtrack(start, tmp, candidates):
            if sum(tmp) > target or start >= len(candidates): return 
            if sum(tmp) == target:
                result.append(tmp[:])
                return
            for i in range(start, len(candidates)):
                tmp.append(candidates[i])
                backtrack(i, tmp, candidates)
                tmp.pop()
                
        backtrack(0, [], candidates)
        return result
                                        
S = Solution()
print(S.combinationSum([2, 3, 6, 7], 7))

LeetCode 216. 组合总和

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result = []
        def backtrack(start, state, n):
            if sum(state) > n or len(state) > k: return 
            if sum(state) == n and len(state) == k:
                result.append(state[:])
                return 
            for i in range(start, 10):
                state.append(i)
                backtrack(i+1, state, n)
                state.pop()

        backtrack(1, [], n)
        return result 

S = Solution()
S.combinationSum3(3, 7)

LeetCode 78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [] 
        n = len(nums)
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j+1, tmp+[nums[j]])
        helper(0, [])
        return res
S = Solution()
S.subsets([1, 2, 3])