关于回溯法中子集树和排列树的问题

Question

bobo老师你好，关于回溯法中子集树和排列树的问题：

        最近学习回溯常常使用到，子集树和排列树，一直有个异或就是 使用到子集树和排列数不一定就是用了回溯吧？还有就是子集树是度为2的二叉树吗？之前使用排列树写出了N后问题，N后问题也可以用子集树写吗？

Answer 1

liuyubobobo 2020-01-02 06:52:32

其实我个人不建议记忆“子集树”或者“排列树”这样的概念。因为这些不是真实的数据结构。实际上，在你发表这个问题之前，我根本没听说过这样的概念。

我的建议是，仔细编写以下两个问题的代码，仔细比较其中的异同：

1 求一个数组的全部子集

2 求一个数组的全部排列

这两个问题，这个课程都有介绍。

如果你仔细分析两个代码，就会明白，其中的区别不是数据结构的区别，而是因为求得内容不同，而自然而然带来的逻辑上的区别。

具体到 n 皇后问题，因为解是每一行每个皇后要放在一列上，并且这些列数不能重复，所以本质是在求 1-n 的一个排列，不能使用求子集的方式求解。

依然是，这些结论不是记忆的结果，而是根据问题自然而然得到的结论，是问题的解空间决定的。请仔细体会这一点。

继续加油！：）

• 提问者 程序员不会说方言 #1

  非常感谢！