(Medium #46) Permutations

Problem

Given a collection of distinct integers, return all possible permutations.

Example:

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

My solution

class Solution:

    def permute(self, nums):

        nums.sort()

        start_nums = nums[:]

        pre_nums = nums[:]

        result = [start_nums]

        while True:

            next_nums = self.nextPermutation(pre_nums)[:]

            if next_nums != start_nums:

                result.append(next_nums)

                pre_nums = next_nums[:]

            else:

                break

        return result

    def nextPermutation(self, nums):

        for i in range(len(nums) - 1, 0, -1):

            if nums[i] > nums[i - 1]:

                start = i - 1  # 4

                # print("start", i-1)

                for k in range(len(nums) - 1, start, -1):

                    if nums[k] > nums[start]:  # 5

                        # print("end", k)

                        end = k

                        nums[start], nums[end] = nums[end], nums[start]  # 4, 5를 바꾼다

                        # print(nums)

                        # nums = nums[:start+1] + nums[:start:-1]

                        for m in range(int((len(nums) - start) / 2)):  # 역순

                            # print(start+1+m, len(nums)-1-m)

                            nums[start + 1 + m], nums[len(nums) - 1 - m] = nums[len(nums) - 1 - m], nums[start + 1 + m]

                            # print("mod",nums)

                        # print(nums)

                        break

                break

            if i == 1:

                nums.reverse()

        return nums

Runtime: 40ms, Memory: 14.2MB