[리트코드] 46. Permutations

# 문제 설명

서로 다른 정수로 이루어진 배열을 입력받아, 모든 가능한 순열을 반환해라.

 

# 입출력 예시

입력	출력
[1,2,3]	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[0,1]	[[0,1],[1,0]]
[1]	[[1]]

 

# 코드 풀이 1.  DFS로 풀기

from collections import defaultdict

class Solution:
    def __init__(self):
        self.cp = []
    
    # 첫번째 노드에 대한 트리
    def visit_path(self, i, path, visited, nums):
        visited[i] = True # 방문 표시
        path.append(nums[i])
        
        if len(path) >= len(nums): # 탈출 조건
            self.cp.append(path)
        else:
            for j, x in enumerate(nums): # 다른 선택지들
                if not visited[j]: # 복사해야함!!
                    self.visit_path(j, path[:], visited[:], nums)
        
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        visited = [False]*n # 1개의 상태공간을 위한 방문여부
        for i in range(n): # 시작노드 선택지
            self.visit_path(i, [], visited[:], nums)
        return self.cp

 

 

방문했는지 여부 visited 없이, 시작노드도 선택해야 하므로 다음과 같이 최적화할 수 있다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
    	cp = []
        prev = []
        
        def dfs(elements): # 앞으로 갈 곳들
            if not len(elements): # 단말노드일 경우
            	cp.append(prev[:])
            
            for e in elements: # 순열 생성 재귀호출
            	next_e = elements[:]
                next_e.remove(e) # 현재노드 다녀옴
                prev.append(e) # 첫번째 노드
                
                dfs(next_e)
                prev.pop()
        
        dfs(nums)
        return cp

 

# 코드 풀이 2.  내장함수로 풀기

from itertools import permutations

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

 

 

# 핵심 포인트

- 첫 번째 방문할 노드부터 선택을 해야하므로, for문 내에서 방문하는 연산을 취한다.

- 방문한 노드 경로 path와 방문 여부 visited (or 남은 노드들 elements)는 반드시 복사하여 넘겨주어야 한다.

- 재귀호출을 사용하는 경우, 탈출 조건과 어떻게 다음 노드와 이어줄 지를 생각해야 한다.