DFS(深度优先搜索)的核心思想是沿着一条路径深入探索,直到无法继续时回退一步,尝试寻找其他未探索的路径。如果依然无路可走,就再次回退,重复这一过程,直到所有可能的路径都被探索完毕。
递归的思想是通过不断调用自身函数,逐层深入解决问题。当满足终止条件时,停止递归并开始逐层回溯。其原理与深度优先搜索的探索与回溯过程高度一致,因此递归是实现深度优先搜索的常用方法。
我们来看看样例是怎么具体实现的
3
题目描述:
给定一个包含 n 个不同整数的数组 nums
,请你使用深度优先搜索(DFS)算法,输出数组中所有可能的排列结果。
排列中的每个元素必须是唯一的,按照字典序的顺序排列
输入:
n
(1 ≤ n ≤ 9),表示数组中元素的个数。n
个不同的整数,表示数组 nums
中的元素,数组中的元素均为整数,且满足绝对值不超过 104。输出:
输出所有可能的排列,每行输出排列。排列中的数字间用空格隔开。
字典序说明:
对于两个不同的字符串,从左到右逐个比较它们的字符:
如果在某个位置上它们的字符不同,则将它们按照位置上的字符的字母顺序进行排序,即较小的字符排在前面,较大的字符排在后面。
如果一直比较到其中一个字符串结束,则较短的字符串排在前面;
如果两个字符串完全相同,则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排序的。
本道题的把数组每个数字看作一个字符,通过字典序比较。
输入示例:
3
1 2 3
输出示例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1