回溯的本质是穷举,穷举所有可能,然后选出想要的答案,如果想让回溯法高效一些,需要进行剪枝操作。
回溯法,一般可以解决如下几种问题:
- 组合问题:N 个数里面按一定规则找出 k 个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个 N 个数的集合里有多少符合条件的子集
- 排列问题:N 个数按一定规则全排列,有几种排列方式
- 棋盘问题:N 皇后,解数独等等
组合不强调元素顺序,排列强调元素顺序:
即 不同顺序的同样元素集合 算作排列,但不算组合
回溯的本质是穷举,穷举所有可能,然后选出想要的答案,如果想让回溯法高效一些,需要进行剪枝操作。
回溯法,一般可以解决如下几种问题:
组合不强调元素顺序,排列强调元素顺序:
即 不同顺序的同样元素集合 算作排列,但不算组合