题目描述

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

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

我的解法——DFS（AC）

第一次往链表添加一个元素，有n中可能，然后将剩下的元素再添加一个元素到链表中，有n-1种可能，以此类推，直至链表中的元素大小等于数组大小。
时间复杂度O(n)，空间复杂度O(n)
Beat 4%

class Solution(object):
    def __init__(self):
        self.res = []
        
    def dfs(self, rest, now):
        length = len(rest)
        if(length == 0):
            self.res.append(now)
            return
        
        for i in range(length):
            self.dfs(rest[:i] + rest[i + 1:], now + [rest[i]])
            
            
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.dfs(nums,[])
        return self.res

最优解法

遍历字符串，然后将当前遍历的字符和首字符交换位置，调用本函数处理首字符之后的子字符串，函数执行完后，再调换回来。在不需要复制字符串的情况下，避免了每次递归函数相互之间的影响。