문제

46. Permutations

Medium

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

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

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

풀이

itertools 내장 모듈을 이용한 풀이

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

위의 문제는 중복되지 않는 모든 수열을 찾는 문제로서, Python의 내장모듈 itertools.permutations 메소드를 이용하여 쉽게 모든 순열의 리스트를 찾을 수 있다.

dfs의 백트래킹을 이용한 풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
    	# 모든순열의 리스트 초기화
        result = []
        # 각 순열 리스트 초기화
        prev_lst = []
        
        # dfs 탐색
        def dfs(elements):
        	# base case
            if len(elements) == 0:
            	# prev_list를 append하면 prev_list의 결과값을 참조하는 것이 아니라 
                # prev_list에 대한 참조가 추가된다.
                # 그래서 prev_list를 카피떠서 추가한다.
                result.append(prev_lst[:])
                return
            
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
                
                prev_lst.append(e)
                dfs(next_elements)
                prev_lst.pop()
        
        dfs(nums)
        
        return result

• dfs탐색과 백트래킹을 이용하여 모든 순열을 찾는 풀이이다.