0. 总结

回溯法常用来解决排列、组合、子集等问题，它以DFS（深度优先）方式构造一棵树，树的路径就是我们要的结果。

解题的首要条件是你要将示例的树构造出来，然后可能涉及以下几个要素：

1. 初始路径为空集：即我们从空节点开始构造树；
2. 以某种条件保存（路径）结果：比如 子集问题我们无条件输出结果，排列问题当路径长度等于数组长度时输出结果，组合问题要去了重后再输出结果；
3. 循环下递归：循环的目的是取遍当前节点的所有子节点，当子节点只有两个时，循环可以省略，这时你需要分别递归两个子节点，就像二叉树一样；递归就是要递归构造树；
4. 循环的候选集：循环时，循环可以取的候选一定要搞清楚；可以根据示例分析，空集（根）的子节点可能包含哪些，某个子节点的子节点又有哪些候选；
5. 递归：选择某个子节点添加到路径后，递归下去；

下面的4个问题的解法都遵循上述套路。

1. 子集

78. subsets

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]

        方法
            回溯法, 循环内递归, 即DFS
            https://pic.leetcode-cn.com/a4f4acf7177b6a1131b1ef5da97c1dae218f3c34e9418219055c729c90300122-image.png
            求子集就是在递归生成一棵树, 一条一条路径、一个一个节点
            遍历, 当前路径path增加了各个可能元素后, 再递归考虑下个元素
            下个元素的取值范围很重要
        """
        result = []

        def backtrack(path, idx):  # 已经有path的情况下, 考虑增加第idx位置的元素
            result.append(path)
            for i in range(idx, len(nums)):
                backtrack(path+[nums[i]], i+1)

        backtrack([], 0)  # 初始path为空集, 考虑增加第0个元素
        return result

2. 全排列

46. permutations

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]

        方法
            回溯法, DFS
            遍历一棵树, 类似于求所有子集那道题
            https://pic.leetcode-cn.com/9d228e7ee9c0beceb48983717e253fd0cd6ba96ef76d06758451a1d4af651c36-image.png
            
        """
        result = []

        def backtrack(path):
            if len(path) == len(nums):  # path长度与nums相等时, 输出
                result.append(path)
                return
            for num in set(nums) - set(path):  # 遍历所有可以增加的元素(排除掉已经在path里面的)
                backtrack(path+[num])
        
        backtrack([])  # 从空集开始增加元素
        return result
        

3. 括号生成

22. generate-parentheses

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        
        方法
            生成潜在的可能结果排列组合, 然后一个一个排除
            排除的过程可以使用辅助栈
        """
        def judge_valid(parenthesis):
            stack = []
            for char in parenthesis:
                if char == '(':
                    stack.append(char)
                else:
                    if not stack:  # 栈为空就想出, 不合法
                        return False
                    stack.pop()
            return True if not stack else False  # 栈不为空, 不合法
        
        result = []

        def backtrack(path):
            if len(path) == 2*n:
                if judge_valid(''.join(path)):
                    result.append(''.join(path))
                return
            if path.count('(') < n:  # for循环递归被替换成两个递归并列
                backtrack(path+['('])
            if path.count(')') < n:
                backtrack(path+[')'])
        
        backtrack([])
        return result
        

4. 组合总和

39. combination-sum

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]

        思路
            组合, 组合跟排列相比不考虑顺序, 所以一定要对结果去重
            回溯时限制和不能大于target, 当等于target时输出
        """
        def backtrack(path, cur_sum):
            if path and cur_sum == target:
                path.sort()
                if str(path) not in tmp_set:
                    result.append(path)
                    tmp_set.add(str(path))
            elif path and cur_sum > target:
                return
            for candidate in candidates:  # 有放回全排列, 注意重复元素
                backtrack(path+[candidate], cur_sum+candidate)
        
        result = []
        tmp_set = set()  # 用于去重, 最终结果里面[2, 2, 3]与[2, 3, 2]、[3, 2, 2]是同一个
        backtrack([], 0)
        
        return result