리트코드 46번 permutations (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

DFS

from typing import List

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

        def dfs(n_list):
            if len(n_list) == len(nums):
                return answer.append(n_list)

            for n in nums:
                if n not in n_list:
                    dfs(n_list + [n])
                    
        for num in nums:
            dfs([num])

        return answer

dfs를 이용하면 쉽게 permutation을 구현할 수 있다.

itertools

from typing import List
from itertools import permutations

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

Reference

파이썬 알고리즘 인터뷰 34번