[LeetCode] #46. Permutations (python)

문제

https://leetcode.com/problems/permutations/

Permutations - LeetCode

받은 정수 배열로 가능한 모든 순열을 반환해야한다.

 

예시 입출력

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

 

풀이

 

책 풀이

 

1. dfs 활용

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

이전 값인 prev_elements, 다음 값인 next_elements 변수가 있다. prev_elements에 현재값이 추가되고 남은 값들을 가지고 있는 next_elements를 넘기면서 dfs 함수를 재귀호출한다. 자식노드가 0일때 결과값에 추가한다. pop은 순열 1개가 완성되고 나서 prev_elements를 빈 리스트로 만들기 위해서 있다.

결과를 추가할 때 prev_elements[:]로 하는 이유는 값을 추가하기 위해서다. 만약 prev_elements로 하면 값이 할당되는 것이 아니라 참조가 할당된다.

 

 

2. itertools 모듈 사용

import itertools

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

itertools : 반복자 생성에 최적화된 기능을 제공하는 모듈

itertools에서 제공하는 permutations 함수를 사용하면 간단하게 풀 수 있다. 해당 함수가 튜플로 반환하기 때문에 리스트로 변환을 해서 반환해야 한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰