深度优先搜索和回溯结合后的终极模板

1 回顾

昨天这5道算法题 都可以套用这个模板推送了一个深度搜索和回溯结合的题目和另4道类似题，今天，逐个分析后4道题，最后提炼出模板。

2 分析4道题

1) 集合内元素都不相同，求子集，举一个例子：

实现代码：

用上面代码跑出的打印出的结果如下所示，如上代码所示，因为是深度优先搜索，把以1为根的所有子集先找出，在找出以2为根的所有子集，最后找出以3为根的所有子集。

短短的几行代码足以实现，可见递归的简洁性。

2) 集合内元素可能相同，求子集

实现代码仅与上面【集合内元素都不相同，求子集】有一个差别：处理1和第一个2，1和第二个2的情况只取一种。

打印结果的顺序如下：

3) 求集合的不同组合序列

在以上求子集的题目基础上，这个就比较简单了，只取与原来长度相等的序列且要回溯，代码如下：

这个含有重复元素的全排序难点在于处理重复元素时的技巧，此处采用一个判断元素当前是否位于栈中的布尔数组。

4) 回文数那道题目，大家自己想一想用上面的模板怎么求解

3 模板

代码模板，详见文字说明

学知识，送红包系列活动

预知是否获得红包，请参考获奖名单。

Python与机器学习算法频道

欢迎点赞和转发