points:
1 是一个不断试错的算法
2 采用递归思想 在进入下一层后 会进行一次回溯(将该层更改的复原 方便进行别的方向的试错)
看到题目如何想到回溯:
题目要求返回输入的所有子集
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
题目要求返回整数[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
全排列
题目要求返回给定数组的所有排列方式,可以像画树一样一个一个画下来,在使用过的数字上打上使用过的标记,挨个往里添加元素,如图所示,确定了一个元素之后往下遍历直至递归终止条件开始回溯
代码
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