NeetCode 150 [Backtracking]medium:Permutations

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