网站建设服务谁便宜,南通关键词优化平台,宿州做企业网站公司,制作网页的超文本标记语言77. 组合
第一次专门做回溯#xff0c;有点难理解。首先可以理解回溯可以可视化为树的搜索#xff0c;因此这道题#xff0c;树的宽度为n#xff0c;树的深度为kpath作为一个参数传入有点难想回溯没有返回值剪纸更难想#xff0c;通过列算式可以勉强得到for的表达式…77. 组合
第一次专门做回溯有点难理解。首先可以理解回溯可以可视化为树的搜索因此这道题树的宽度为n树的深度为kpath作为一个参数传入有点难想回溯没有返回值剪纸更难想通过列算式可以勉强得到for的表达式但是要自己写出来还是有点难
class Solution:def combine(self, n: int, k: int) - List[List[int]]:# 递归的话就是取一个数然后递归为k-1self.output []self.backtracking(n, k, 1, [])return self.output# start_index表示从哪里开始遍历def backtracking(self, n, k, start_index, path): # path用来记录遍历的路径if len(path) k: # 当路径长度k时输出相当于遍历到了叶子节点self.output.append(path[:]) # 为啥这里时path就不行for i in range(start_index, n1):path.append(i)self.backtracking(n,k,i1,path)path.pop() # 回溯剪枝后
class Solution:def combine(self, n: int, k: int) - List[List[int]]:result [] # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) k:result.append(path[:])returnfor i in range(startIndex, n - (k - len(path)) 2): # 优化的地方path.append(i) # 处理节点self.backtracking(n, k, i 1, path, result)path.pop() # 回溯撤销处理的节点需要多做做题找找感觉
