[Leetcode] 리트코드 - 순열(permutations) 파이썬(python) 풀이

문제

서로 다른 정수를 입력 받아 가능한 모든 순열을 리턴하라.
입력

[1,2,3]

출력

[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]

코드

재귀 함수

from typing import List


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

        def dfs(elements):
            if len(elements) == 0:
                results.append(prev_elements[:])

            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()

        dfs(nums)
        return results

itertools 모듈

import itertools

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

풀이

재귀함수

순열이란 결국 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있기 때문에 그래프로 표현가능하다.

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

        def dfs(elements):
            if len(elements) == 0:
                results.append(prev_elements[:])
                print(f'results : {results} dfs 종료')
                print()

            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)
                print(f'elements : {elements}, prev_elements : {prev_elements}, next_elements : {next_elements}, dfs 호출')
                dfs(next_elements)
                prev_elements.pop()

        dfs(nums)
        return results

-------------------------------------
elements : [1, 2, 3], prev_elements : [1], next_elements : [2, 3], dfs 호출
elements : [2, 3], prev_elements : [1, 2], next_elements : [3], dfs 호출
elements : [3], prev_elements : [1, 2, 3], next_elements : [], dfs 호출
results : [[1, 2, 3]] dfs 종료

elements : [2, 3], prev_elements : [1, 3], next_elements : [2], dfs 호출
elements : [2], prev_elements : [1, 3, 2], next_elements : [], dfs 호출
results : [[1, 2, 3], [1, 3, 2]] dfs 종료

elements : [1, 2, 3], prev_elements : [2], next_elements : [1, 3], dfs 호출
elements : [1, 3], prev_elements : [2, 1], next_elements : [3], dfs 호출
elements : [3], prev_elements : [2, 1, 3], next_elements : [], dfs 호출
results : [[1, 2, 3], [1, 3, 2], [2, 1, 3]] dfs 종료

elements : [1, 3], prev_elements : [2, 3], next_elements : [1], dfs 호출
elements : [1], prev_elements : [2, 3, 1], next_elements : [], dfs 호출
results : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] dfs 종료

elements : [1, 2, 3], prev_elements : [3], next_elements : [1, 2], dfs 호출
elements : [1, 2], prev_elements : [3, 1], next_elements : [2], dfs 호출
elements : [2], prev_elements : [3, 1, 2], next_elements : [], dfs 호출
results : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] dfs 종료

elements : [1, 2], prev_elements : [3, 2], next_elements : [1], dfs 호출
elements : [1], prev_elements : [3, 2, 1], next_elements : [], dfs 호출
results : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] dfs 종료

위의 코드와 같이 dfs함수를 따라가면 dfs가 호출될 때마다 prev_elements, next_elements, elements를 확인할 수 있다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]