通常如果需要列出所有的结果的时候，就需要使用回溯法(backtracking)。当然通过暴力解法(brute force)也是可以，但是暴力解法会浪费太多的时间和空间。两点区别

1. 回溯法会回头，把路径pop出来，而暴力解法是走所有的解
2. 回溯法会剪枝，比如通过某些if条件滑过某些路径，减少很多不必要走的路

识别回溯

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。 一般回溯的问题有三种：

1. 有没有解：Find a path to success
2. 求所有解：Find all paths to success 求所有解的个数 求所有解的具体信息
3. 求最优解：Find the best path to success

backtracking代码模板

'''
backtracking使用dfs的模板，基本跟dfs的模板一模一样
'''
class Backtracking(object):

    def backtracking(self, input):

        self.res = []

        def dfs(input, temp, [index]):
            # 边界
            if 非法数据：
                return

            # 终止条件
            if len(input) == len(temp)：
                self.res.append(temp[:])
                return

            # for循环
            for i range(len(input)):
                ##1. 修改path
                temp.append(input[i])
                ##2. backtracking
                dfs(input, temp, [index])
                ##3. 退回原来状态，恢复path
                temp.pop()
        # 执行
        dfs(input, [], 0)
        return self.res

深度搜索与回溯法的区别

简单一点可以认为　回溯法 = 深度搜索 + 剪枝。一般大家用深度搜索时，或多或少会剪枝，因此深度搜索与回溯法没有什么不同，可以在它们之间画上一个等号。简单的可以认为二者等价。

深度搜索一般用递归(recursion)来实现，这样比较简洁。

深度搜索能够在候选答案生成到一半时，就进行判断，抛弃不满足要求的答案，所以深度搜索比暴力搜索法要快。

深度搜索与递归的区别

深度搜索经常用递归(recursion)来实现，二者常常同时出现。深度搜索，是逻辑意义上的算法，递归，是一种物理意义上的实现，它和迭代(iteration)是对应的。深度搜索，可以用递归来实现，也可以用栈来实现；而递归，一般总是用来实现深度搜索。可以说，递归一定是深度搜索，深度搜索不一定用递归。