#回溯问题模版框架 result = [] defbacktrack(当前路径,选择列表): if 满足结束条件:#比如选择列表为空 result.append(当前路径) return for 选择 in 选择列表: 做选择(将此选择从选择列表移除) backtrack(当前路径,新选择列表) 撤销选择(将上一步做出的选择从路径列表剔除,加入选择列表)
leetcode 797,77
子集问题利用回溯算法,要用 index 参数排除已选择的数字。
组合问题利用回溯思想,结果可以表示成树结构,关键点在于要用一个 index 排除已经选择过的数字。
排列问题利用回溯思想,也可以表示成树结构,关键点在于使用 contains 方法排除已经选择的数字
全排列
—新版—
排列的结束条件是选择列表的每个元素都被选择过一次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
res = [] choices = [1,2,3] curpath = [] defbacktrack(curpath,choices): if len(choices) == len(curpath): res.append(curpath.copy()) #需要传递下curpath的拷贝,否则对curpath的修改会影响到res结果 return
for i in range(len(choices)): if choices[i] in curpath:#跳过已经作出的选择 continue#若是有放回抽样,就注释掉这个if语句 curpath.append(choices[i]) backtrack(curpath,choices) curpath.pop() backtrack(curpath,choices) print(res) #[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
for i in range(index,len(choices)): curpath.append(choices[i]) backtrack(curpath,choices,i+1) #注意是i+1 curpath.pop() backtrack(curpath,choices,index=0) print(res) #[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
组合
组合与子集差不多,区别在于结束条件,组合和排列必须是树的叶子结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
res = [] choices = [1,2,3,4]
defbacktrack(curpath,choices, index, k): if len(curpath) == k: res.append(curpath.copy()) return for i in range(index, len(choices)): curpath.append(choices[i]) backtrack(curpath.copy(),choices,i+1, k) curpath.pop()