回溯算法

关于穷举，一直都是我忽略的，今天来专门学习下

解决一个回溯问题，本质上一个遍历决策树的过程

（1）路径：已经作出的选择

（2）选择列表：当前可以做的选择

（3）结束条件：无法继续做选择的条件

回溯算法的基本框架

1 2 3 4 5 6 7 8 9 10

result = [] def backtrack(路径，选择列表)： if 满足条件 result.add(路径) return for 选择 in 选择列表 做选择 backtrack(选择，选择列表) 撤销选择

问题一：子集

$\mathrm{input:}$ 一个不包含重复数字的数组

$\mathrm{output:}$ 这个数组中数字所组成的子集

---

• ← Previous Post
• Next Post →