leetcode [46] 全排列

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例:

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

解法一：参考leetcode 31 下一个排列，先排序，从头开始进行下一个排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        
        result = []
        nums.sort()
        result.append(nums)
        while True:
            nums = nums.copy()
            low = len(nums) - 1
            for i in range(len(nums) - 2, -1, -1):
                if nums[i] < nums[i + 1]:
                    low = i
                    break
            high = len(nums) - 1
            for i in range(len(nums) - 1, low, -1):
                if nums[low] < nums[i]:
                    high = i
                    break
            nums[low], nums[high] = nums[high], nums[low]
            if low + 1 < len(nums):
                nums[low + 1:] = nums[low + 1:][::-1]
            if nums == result[-1]:
                break
            else:
                result.append(nums)
        return result

解法二：全排列=单个元素+除该元素后的全排列，递归，终止条件为两个元素两种全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0: return []
        if len(nums) == 1: return [nums]
        if len(nums) == 2: return [[nums[0], nums[1]], [nums[1], nums[0]]]

        ans = []
        for i in range(len(nums)):
            res = self.permute(nums[:i] + nums[i + 1:])
            for r in res:
                ans.append([nums[i]] + r)

        return ans