leetcode题解46：全排列

描述

该题来自于力扣第46题

分析

子问题分解，比如说要排列1 2 3，那就先取1，全排列2 3，得到1 2 3和1 3 2，依次下去，直到取完所有的数字。相当于全排列n个数，可以先求n-1个数的全排列，分解成一个子问题，显然用递归求解非常简单。

至于代码上的编写技巧，非python，取第i个数时，可以先与第0个数交换，然后排列数组的后n-1位，最后再交换回来就可以了。

代码

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]
        res = []
        for i in range(len(nums)):
            for subres in self.permute(nums[:i] + nums[i+1:]):
                res.append([nums[i]] + subres)
        return res