[리트코드(LeetCode)] 46번 Permutations

문제

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

Permutations - LeetCode

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

예시

Example 1:

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

 

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

 

Example 3:

Input: nums = [1]
Output: [[1]]

풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(elements):
            if len(elements) == len(nums):
                res.append(elements[:])
                return

            for i in nums:
            # 중복된 순열 방지
                if i not in elements:
                    elements.append(i)
                    dfs(elements)
                    elements.pop()

        res = []

        dfs([])
        
        return res

 

- 깊이 우선 탐색(DFS)을 사용하여 모든 순열을 생성한다.

- dfs 함수에서 'elements'는 현재까지의 순열을 나타내고 현재 순열의 길이가 nums의 길이와 같을 때 결과 리스트에 추가한다.

- 현재 순열에 포함되지 않은 각 요소에 대해 반복하면서 해당 요소를 현재 순열에 추가하고 재귀 호출하고, 다시 해당 요소를 제거하여 이전 상태로 돌아간다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview