关于回溯法中子集树和排列树的问题
来源：8-5 回溯法解决组合问题的优化
程序员不会说方言
2019-12-30
bobo老师你好，关于回溯法中子集树和排列树的问题：
最近学习回溯常常使用到，子集树和排列树，一直有个异或就是 使用到子集树和排列数不一定就是用了回溯吧？还有就是子集树是度为2的二叉树吗？之前使用排列树写出了N后问题，N后问题也可以用子集树写吗？
写回答
1回答
-
其实我个人不建议记忆“子集树”或者“排列树”这样的概念。因为这些不是真实的数据结构。实际上，在你发表这个问题之前，我根本没听说过这样的概念。
我的建议是，仔细编写以下两个问题的代码，仔细比较其中的异同：
1 求一个数组的全部子集
2 求一个数组的全部排列
这两个问题，这个课程都有介绍。
如果你仔细分析两个代码，就会明白，其中的区别不是数据结构的区别，而是因为求得内容不同，而自然而然带来的逻辑上的区别。
具体到 n 皇后问题，因为解是每一行每个皇后要放在一列上，并且这些列数不能重复，所以本质是在求 1-n 的一个排列，不能使用求子集的方式求解。
依然是，这些结论不是记忆的结果，而是根据问题自然而然得到的结论，是问题的解空间决定的。请仔细体会这一点。
继续加油！：）
012020-01-02
相似问题