算法之 回溯一

请看需求

给定一个没有重复数字的序列，返回其所有可能的全排列。示例:

输入:[1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

---

---

我们使用回溯法实现一下，一般法不写了，不说了，看图

图片源自网络

解释:

第一步，我们选择一个数字，比如1

第二步，就只能从2和3中间选择了，我们选择2，组成12

第三步，这次只有3了，没的选了，于是组成123

123就是一个结果，我们将其保存，这时候我们将第三步中的3删除，然后再回退到第二步(回溯)

由于在第二步中，我们已经选过2了，那么此时就只剩3让我们选了。

于是我们再次组成13

之后再次进入到第三步，这次只有2了，于是组成132

我们需要拼出1，通过1生成1,2和1,3

之后通过1,2生成1,2,3

通过1,3生成1,3,2

这里我们借助栈和队列的组合，实现的。

代码是基于来自IT界的泥石流修改而来

---

def  dfs(nums,arr):

        result =[]

      if len(nums)==0:

          Print(arr)

size=len (nums)

for  k  in  range (size):

      arr.append(nums.pop(k))

    dfs (nums,arr)

      nums.insert(k,arr.pop())

nums=[1,2,3]

arr=[]

dfs (nums,arr)