共计 1666 个字符，预计需要花费 5 分钟才能阅读完成。
搜寻实质上也是对解空间的枚举，本文介绍搜索算法中的深度优先搜寻（图论）。
全排列问题
给定一个 没有反复数字 的序列，返回其所有可能的全排列。例如对于数列 [1, 2, 3] 其全排列为[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。
咱们能够应用 n 层循环，每一层循环内确定一位数字，在最内层循环内判断该排列是否符合要求，例如对于数列 nums = [1, 2, 3]，能够写出如下代码。
for i in nums:
for j in nums:
for k in nums:
if i != j and j != k and i != k:
print i, j, k这道题目剖析到这里，其实和我的第一篇文章的问题很有很大类似的中央，但不同的是在于百鸡百钱问题的自变量个数是固定的，即循环层数是固定的。
上述代码中咱们试图通过每一层循环来确定一个数值，但这段代码只实用于 len(nums) == 3 的状况，然而如果 nums 长度为 4，5，或更高呢？咱们无奈动静生成 n 层循环，除非是用程序编写程序，递归为咱们奇妙地解决了这个问题。
在递归中，咱们则通过每一层函数的嵌套来确定一个数值，并且咱们只需给出顶层的实现就够了。
于是咱们得出了上面的代码（波及 python 中 list 与 set 的应用）。
def solution(nums, status):
if set(nums) == set(status):
print status
for x in nums:
solution(nums, status+[x])上述代码中，status 示意以后函数档次的状态，即一个排列后果，该递归函数能够了解为一个数学表达式：solution = for + solution，那么该 solution 函数就会被开展为上面的样子。
for ... in range(...):
for ... in range(...):
...
if ... : print ... # 只有在第 n 层，条件才会成立这就和咱们最开始给出的代码看上去差不多了。然而当初代码尽管是无限的，可理论开展的时候仍旧是无穷无尽的，这就须要咱们为 solution 函数加上一个终止条件，也称 递归进口。
如果把递归的过程设想成包子馅的包子，那么如果没有递归进口，这个包子将会变成馒头。
那么递归进口咱们如何去定义呢？
通过题意不难推出当对于以后层，若以后排列后果 status 长度大于 nums 数列长度，即可终止递归。
于是可得出正确代码如下。
def solution(nums, status):
if len(status) > len(nums):
return
if set(nums) == set(status):
print status
for x in nums:
solution(nums, status+[x])
solution([1,2,3], [])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]这段代码尽管能够正确运行，但咱们能够让他更加好看。最终代码如下。
这一次，咱们将递归进口定义在进入递归函数前，并且将中间状态记录在了 ans 数组中。
def solution(nums, status, ans):
if len(nums) == len(status):
ans.append(status)
for x in nums:
if x not in status:
solution(nums, status+[x], ans)
return ans
print solution([1,2,3], [], [])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]如果在 solution 的开始输入 status 的值，咱们会失去如下的输入后果。
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
[2, 3]
[2, 3, 1]
[3]
[3, 1]
[3, 1, 2]
[3, 2]
[3, 2, 1]察看程序的输入与上面的图片，领会该迭代办法被称作 深度优先搜寻 的起因。
本文示例题目与 leecode 46. 全排列统一，读者可自行尝试提交，验证本人代码的正确性。
