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

1 回顾

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

2 分析4道题

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

实现代码:

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

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

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

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

打印结果的顺序如下:

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

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

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

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

3 模板

代码模板,详见文字说明

学知识,送红包系列活动

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

Python与机器学习算法频道

欢迎点赞和转发

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180714G1JD1H00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券