回溯树求集合全排列和所有子集

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,深度搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 踏上算法之路,风景这边独好!

01

通过这篇文章,你学到什么

通过这篇文章,我们可以进一步体会到深度优先搜索算法在具体问题中的应用,通过详细地示意图,深刻明白递归调用时的进栈,出栈过程;最后通过Leetcode 相似解法的题目进一步加深对深度搜索算法的理解。

02

搜索算法

搜索算法,常见的几种形式,深度优先,广度优先,二分搜索,应用搜索算法的前提是求解空间是有限的,然后在这个空间中找出满足题意的解。有些问题如果能用二分搜索,那是最高效的,因为每次都会使求解空间减掉一半。

03

DFS

Depth first search algorithm,它是首先沿着深度方向搜索,然后再在广度方向搜索的。例如,要求某个序列的全排列,就可以用深度优先搜索。

04

全排序深度搜索算法

1 某个序列的全排序算法题目

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321"

2 题目分析

如何写出深度优先搜索的代码呢?

  1. 首先我们拿出元素1,然后在1,2,3 这个深度方向寻找,找到满足题意的解有两个,1,2,3,和1,3,2;
  2. 然后再在广度方向上搜索,此时的元素为2,再在1,2,3 深度方向上搜索,得到满足题意的解,2,1,3和2,3,1,
  3. 最后,在广度方向上搜索到3,再在1,2,3 深度方向上搜索,满足题意的解为 3,1,2 和 3,2,1。

3 源码实现

public class Solution
    {
        public IList<IList<int>> GetPermutation(int n)
        {
            IList<IList<int>> rslt = new List<IList<int>>();
            dfs(rslt, new List<int>(),1,n);
            return rslt;
        }
 // start 是dfs抽出的一个关键参数
        private void dfs(IList<IList<int>> rslt, 
                                 List<int> curItem, 
                                 int start,
                                 int digits)
        {
  //找到一个解
  if (curItem.Count == digits) 
            {
                rslt.Add(new List<int>(curItem));
                return;
            }
  //广度方向搜索
            for (int i = 1; i <= digits; i++) 
            {
 //跳过重复元素
                if (curItem.Contains(i))
                    continue;
                curItem.Add(i);
 //深度方向上的递归
                dfs(rslt, curItem, i,digits); 
 //后进栈的元素优先出栈
                curItem.RemoveAt(curItem.Count - 1); 
            }
        }
    }
05

图解源码

dfs递归调用的进、出栈示意图

dfs 在深度方向递归进、出栈过程,广度方向首先遍历到1,但是不展开,而是在深度方向展开,1,2,3 的 dfs 依次入栈,出栈顺序依次为 3,2,1,1,如下图所示,

然后再在广度方向上搜索【补充,可以看出深度优先搜索在前,广度方向上搜索在后,所以叫做 DFS】,此时 广度方向 for 遍历到 i = 2,然后再在深度方向搜索,出栈顺序依次为 3,2,1,2,如下图所示,

同理,广度方向搜索到 i=3,然后再在深度方向搜索,出栈顺序依次为 3,2,1,3,如下图所示,

dfs 终止

06

融会贯通

应用这个深度搜索算法思想模板可以解决 LeetCode 上的一类题目,这些题目的解法与本文介绍的全排序搜索算法极为相似,大家不妨看一看,写一写,彻底贯通这个深度搜索算法思想模板。

1 Leetcode 78. Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

2 Leetcode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

3 Leetcode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example, [1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

4 Leetcode 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = “aab”, Return

[ [“aa”,”b”], [“a”,”a”,”b”] ]


看看 Leetcode 上这些应用了 DFS 的题目,这些题目与 讲解的那道题思路非常相似,灵活运用的这个思考过程还是很重要的,仔细体会下吧。

以上答案的链接,请参考如下引用:

http://blog.csdn.net/column/details/14761.html?&page=1

本文分享自微信公众号 - 算法channel(alg-channel)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木可大大

算法初体验

在介绍具体算法之前,我先谈一下个人对学习算法的初心。我的初心无非有两点:一,BAT等互联网公司招聘面试时要问算法知识,如果想要进入互联网公司,我就必须学好算法;...

49090
来自专栏PHP在线

如何计算时间复杂度

求解算法的时间复杂度的具体步骤是: ⑴ 找出算法中的基本语句; 算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。 ⑵ 计算基本语句的执...

30070
来自专栏木可大大

算法初体验

在介绍具体算法之前,我先谈一下个人对学习算法的初心。我的初心无非有两点:一,BAT等互联网公司招聘面试时要问算法知识,如果想要进入互联网公司,我就必须学好算法;...

9630
来自专栏C语言及其他语言

【每日一题】问题 1247: 筛排处理

关注我们 题目描述 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N<=100),对于其中重...

30480
来自专栏落影的专栏

程序员进阶之算法练习(四)

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

474100
来自专栏小红豆的数据分析

小蛇学python(11)初窥numpy

读者可以自行输入,观看结果,享受编码的乐趣。注意zeros和ones后面是跟了两组小括号的。

11130
来自专栏程序员叨叨叨

6.6 条件操作符(Conditional Operators)

expr1的计算结果为true或者flase,如果是true,则expr2执行运算,否则expr3 被计算。

13030
来自专栏HansBug's Lab

算法模板——计算几何2(二维凸包——Andrew算法)

实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

23460
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

假设给定一个由字母和小数点组成的字符串,把字符串按块翻转,其中连续的小数点为一块,连续的字母为一块。例如 'ab..bc...cd.' 翻转后为 '.cd......

26340
来自专栏窗户

围棋规则的计算机实现

  提到这个名字,很多人会想到前段时间让全世界振奋的围棋人工智能Alphago,想曾经我也了解过一些围棋的AI。我也正想花点时间说说alphago相关的东西,包...

306100

扫码关注云+社区

领取腾讯云代金券