[Leetcode] 46. Permutations

문제 바로가기

DFS

Time Complexity: O(n^2)
Space Complexity: O(n^2) - DFS에서 제일 깊은 단계에서 길이 n의 buf가 stack에 n개 올라가므로

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        visited = [False for i in range(n)]
        permutations = []
        
        def DFS(buf: List[int]) -> None:
            if len(buf) == n:
                permutations.append(buf)
                return
            
            for i, num in enumerate(nums):
                if visited[i]:
                    continue
                visited[i] = True
                DFS(buf + [num])
                visited[i] = False
        
        DFS([])
        return permutations

DFS without visited

visited를 기록하는 대신 각 단계에서 사용한 숫자를 제외한 새 list를 전달한다.

Time Complexity: O(n^2)
Space Complexity: O(n^2)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        permutations = []
        
        def DFS(subNums: List[int], path: List[int]) -> None:
            if len(subNums) == 1:
                permutations.append(path + subNums)
                return
            
            for i in range(len(subNums)):
                DFS(subNums[:i] + subNums[i + 1:], path + [subNums[i]])
        
        DFS(nums, [])
        return permutations