Leetcode46 全排列

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
>>输入：nums = [1,2,3]
>>输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
>>输入：nums = [0,1]
>>输出：[[0,1],[1,0]]

示例 3：

1
2
>>输入：nums = [1]
>>输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

image-20240828174049386

终止条件： 当 x = len(nums) - 1 时，代表所有位已固定（最后一位只有 1 种情况），则将当前组合 nums 转化为数组并加入 res ，并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>class Solution(object):
   def permute(self, nums):
       res = []

       def dfs(x):
           if x == len(nums) - 1:
               res.append(list(nums))
               return
           for i in range(x,len(nums)):
               # 交换数值
               nums[i], nums[x] = nums[x],nums[i]
               dfs(x+1)
               # 恢复现场
               nums[i], nums[x] = nums[x], nums[i]
       
       dfs(0)
       return res