[DSA][Backtracking] 04. Permutations

LeetCode 46

 

04. Permutations

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

 

[질문하기]

- 빈 배열이 주어질 수 있나요? NO

 

[아이디어]

- 현재 위치에 올 수 있는 모든 원소를 재귀적으로 swap 하여 순열을 생성한다.

 

 

[풀이 1] Backtracking

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack(nums, 0)
        return self.res
    
    def backtrack(self, nums: List[int], idx: int):
        if idx == len(nums):
            self.res.append(nums[:])
            return
        
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]
            self.backtrack(nums, idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]

순열을 만들기 위해 빈 배열에서 숫자를 하나씩 추가해도 되지만, 이미 존재하는 배열을 in-place로 재배열하면서 추가 공간 없이 각 자리를 확정해 나갈 수도 있다.

backtrack(nums, idx) 함수는 nums 배열에서 idx 번째 위치에 어떤 숫자를 놓을지를 결정하는 함수로, 0 ~ idx-1는 이미 확정된 구간, idx ~은 아직 배치되지 않은 구간이다. 따라서 idx가 nums 길이까지 도달하면 모든 자리가 확정된 것이므로 현재 배열 상태를 하나의 순열로 결과에 추가한다.

idx 위치에 올 수 있는 숫자는 현재 배열의 idx ~ 끝에 있는 모든 값이다. 따라서 for 루프를 통해 각 위치를 순회하면서, nums[idx]와 nums[i]를 swap 하여 i번째 숫자를 idx 자리에 배치하고, 재귀적으로 idx+1을 호출하여 다음 자리의 숫자를 결정하며, 모든 탐색이 끝나면 다시 swap 하여 배열을 원래 상태로 되돌린다.

 

⏱️ 시간복잡도

n개의 원소로 만들 수 있는 순열의 수는 n!이고, 각 순열을 결과 리스트에 추가할 때 리스트 복사로 O(n) 시간이 필요하므로 전체 시간 복잡도는 O(n x n!)이다.

🧠 공간복잡도

이 알고리즘은 in-place 스왑 방식을 사용하므로 재귀 스택을 제외하면 별도의 추가 공간을 사용하지 않는다. 다만, 출력해야 하는 모든 순열을 저장하는 데 n!개의 순열 × 각 순열 길이 n의 공간이 필요하므로 전체 공간 복잡도는 O(n x n!)이다.