NeetCodeのSolutionを書いていく

#

Permutations

#

問題

#

ユニークな正数の配列numsが与えられます。 全てのあり得る順列を返してください。 順番は問いません。

例

#

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

Input: nums = [7] Output: [[7]]

制約

#

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• O(n * n!)
• O(n)

メモ

#

答えの数はn!ですね。 [1,2,3]なら321=6個の回答ができるはず。

loopしながら、選んだものを削除して次のloopを再帰すれば良い？ これだと各ループのための配列を保持するのでメモリもO(n! * n)になってしまうか。 Solutionを見ると、「再帰を使わない」メモリをO(n)で実行する方法が紹介されていた。

from typing import List


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

        def func(nums, input):
            for i, num in enumerate(nums):
                output = input.copy()
                output.append(num)
                copy_nums = nums.copy()
                del copy_nums[i]
                if len(copy_nums) == 0:
                    outputs.append(output)
                    return
                func(copy_nums, output)

        func(nums, [])
        return outputs