题解 | #没有重复项数字的全排列#

这一题看着简单但是写起来一下子还找不到思路，看了下题解也无法一下子理解，大家的方法都比较抽象，花了很久才想出直观的解决该题的思路。 解决算法如下所示：

1. 把第一个元素取出来，记作a；
2. 递归解决剩下的list的全排列，得到结果为[[...],[...],...,];
3. 对于得到的结果进行遍历，然后将元素a插入到得到的结果的每一个位置；

举一个具体的例子来说明，对于list num=[1,2,3],首先取出第一个元素设为a=1，然后递归得到[2,3]的全排列为[[2,3],[3,2]]，遍历[2,3]的全排列，比如第一个[2,3]，把a插入到它的各个位置得到[1,2,3],[2,1,3],[2,3,1],然后在对[3,2]也这样做就搞定了。

但是使用上述的递归方式虽然可以得到全排列，但是依然没法使得得到的全排列按照题目要求的结果输出，因此在将a插入递归返回结果result（[[...],[...],...,]）的过程中还需要做一些处理。将a插入递归返回结果的算法如下：

1. 首先将a插入在result每个元素的第0个位置，即list开头，这是因为a是递归结果任意元素的前面的元素，因此输出结果中一定是在开头的；
2. 按照顺序取出result中的元素，对于result[i]，把a按照顺序插入到第1,...,len(result[i])的位置；

本题的关键还是要理清这个递归的逻辑，也就是先拿出第一个元素，然后递归得到剩下元素的全排列，在把第一个元素插入到剩下元素全排列的每个位置去即可。 这样得到的结果就是满足要求的了，代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num) :
        # write code here
        if len(num)==1:
            return [num]
        else:
            a = num[0]
            result = self.permute(num[1:])
            new_result = []
            leng = len(result[0])
            for i in range(len(result)):
                new_result.append([a]+result[i])
            for i in range(len(result)):
                tmp = result[i]
                for j in range(len(tmp)):
                    if j != len(tmp)-1:
                        new_result.append(tmp[:j+1]+[a]+tmp[j+1:])
                    else:
                        new_result.append(tmp+[a])
        return new_result

num = [1,2,3]
print(Solution().permute(num))