[LeetCode] 46. Permutations (Python)

• Reference
• not in을 사용하는 것보다 dfs의 정석인 visited 로직을 사용하는 게 더 빠름
  • 대신, index가 어쩔 수 없이 필요해짐

Solution

from typing import List


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

        def dfs(elements: List[int]) -> None:
            if len(elements) == len(nums):
                answer.append(elements[:])
                return

            for num in nums:
                if num not in elements:
                    elements.append(num)
                    dfs(elements)
                    elements.pop()

        for num in nums:
            dfs([num])

        return answer

Another Solution

from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        visited = [False] * len(nums)

        def dfs(index: int, elements: List[int]) -> None:
            if len(elements) == len(nums):
                answer.append(elements[:])
                return

            visited[index] = True

            for j, n in enumerate(nums):
                if not visited[j]:
                    elements.append(n)
                    dfs(j, elements)
                    elements.pop()

            visited[index] = False

        for i, num in enumerate(nums):
            dfs(i, [num])

        return answer

IterTools Solution

import itertools
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return itertools.permutations(nums)