回溯法

points：
1 是一个不断试错的算法
2 采用递归思想 在进入下一层后 会进行一次回溯（将该层更改的复原 方便进行别的方向的试错）

经典例题 78

看到题目如何想到回溯：
题目要求返回输入的所有子集
point1：返回子集长度分别是0,1…，len(nums) 每次运行都将层次+1
point2: 回溯的思想 在长度确定的情况下 添加元素 之后要下个层次添加元素 将上个层次添加的元素删除
point3: 递归返回空值 不返回任何元素
point4：不允许重复，直接向后遍历即可

代码：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums,res,index,subset,length):
            if len(subset) == length:
                res.append(subset[:])
                return   #point3 返回空值
            for i in range(index,len(nums)):
                subset.append(nums[i])
                backtracking(nums,res,i+1,subset,length)#point4 向后遍历
                subset.pop() #point2 删除上次添加的元素 进入下个层次
        res = []
        for i in range(len(nums)+1): #point1 层次+1
            backtracking(nums,res,0,[],i)
        return res

经典例题77

题目要求返回整数[1,n]数内 长度为k的任意组合
point1：设置一个数组之后由于题目要求不能重复，即简单的向后遍历，删除，再遍历，经典的回溯过程。
point2:设置往后遍历的层次

代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(nums,res,subset,k,index):
            if len(subset) == k:
                res.append(subset[:])
                return  
            for i in range(index,len(nums)):
                subset.append(nums[i])
                backtracking(nums,res,subset,k,i+1)#point1 point2
                subset.pop()#point1中的回溯 删除元素
        nums = [i for i in range(1,n+1)]
        res = []
        backtracking(nums,res,[],k,0)
        return res

经典例题46

全排列
题目要求返回给定数组的所有排列方式，可以像画树一样一个一个画下来，在使用过的数字上打上使用过的标记，挨个往里添加元素，如图所示，确定了一个元素之后往下遍历直至递归终止条件开始回溯

代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums,res,used,temp):
            if len(temp) == len(nums):
                res.append(temp[:])
                return 
            for i in range(len(nums)):
                if used[i]:
                    used[i] = False
                    temp.append(nums[i])
                    backtracking(nums,res,used,temp)
                    temp.pop()
                    used[i] = True
        res = []
        used = [True for i in range(len(nums))]
        backtracking(nums,res,used,[])
        return res