[코테] 리트코드 그래프 46. Permutations

46. Permutations

문제 링크

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

문제 설명

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

제한 사항

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

입출력 예 #1

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

입출력 예 #2

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

입출력 예 #3

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

문제 풀이

1. dfs 기법을 이용한 수열 출력
2. itertools 모듈의 permutations를 이용한 풀이

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            

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