46-permutations

Try it on leetcode

Description

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Solution(Python)

class Solution:
    #     def permute(self, nums: List[int]) -> List[List[int]]:
    #         res = []

    #         def backtrack(nums,k):
    #             if k == len(nums):
    #                 res.append(nums[:])
    #                 return

    #             for i in range(k,len(nums)):
    #                 nums[i],nums[k] = nums[k],nums[i]
    #                 backtrack(nums,k+1)
    #                 nums[k],nums[i] = nums[i],nums[k]

    #         backtrack(nums,0)

    #         return res
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        times = 1
        for i in range(1, n + 1):
            times *= i

        for i in range(1, times + 1):
            nums = self.nextperm(nums)
            res.append(nums[:])
        return res

    def nextperm(self, nums: List[int]) -> List[int]:
        n = len(nums)

        i = n - 2

        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1

        if i >= 0:
            j = n - 1

            while j >= 0 and nums[i] >= nums[j]:
                j -= 1

            nums[i], nums[j] = nums[j], nums[i]

        # reverse from i+1

        s = i + 1
        e = n - 1

        while s < e:
            nums[s], nums[e] = nums[e], nums[s]
            s += 1
            e -= 1

        return nums