LeetCode

LeetCode 46 Permutations 풀이: 사용 여부를 관리하는 백트래킹

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

입력 원소를 빠짐없이 한 번씩 사용하면서 가능한 모든 순서를 만들어야 한다. 각 위치에 어떤 원소를 놓았는지와 이미 사용한 원소를 관리하고, 한 선택이 끝나면 상태를 복원해야 하므로 백트래킹 이해가 필요한 Level 3 문제로 판단했다.

1. 문제 요약

서로 다른 정수로 이루어진 배열 nums가 주어진다. 배열의 모든 원소를 정확히 한 번씩 사용해 만들 수 있는 모든 순열을 반환해야 한다. 결과의 순서는 어떤 순서여도 된다.

문제의 조건은 다음과 같다.

  • nums의 길이는 1 이상 6 이하이다.
  • 각 원소의 값은 -10 이상 10 이하이다.
  • 모든 원소의 값은 서로 다르다.
  • 각 순열은 입력 원소를 모두 한 번씩 포함해야 한다.

원소가 n개라면 첫 번째 위치에는 n개, 두 번째 위치에는 n - 1개, 마지막 위치에는 1개의 선택지가 있다. 그래서 결과 순열의 개수는 n!개다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

후보 생성과 검증

현재 순열을 path, 각 원소의 사용 여부를 used로 관리한다. 재귀 함수의 상태는 다음과 같다.

  • path: 현재까지 앞에서부터 채운 순열
  • used[i]: nums[i]가 현재 path에 이미 들어갔는지 여부

각 재귀 단계에서 모든 인덱스를 확인하고 아직 사용하지 않은 원소를 후보로 선택한다. 선택한 원소를 path에 추가하고 used[i] = True로 만든 뒤 다음 위치를 재귀적으로 채운다. 재귀 호출이 끝나면 path.pop()과 used[i] = False로 상태를 되돌리고 다음 후보를 시도한다.

path의 길이가 nums의 길이와 같아지면 모든 원소를 한 번씩 사용한 완성된 순열이다. 이때 path.copy()를 결과에 저장한 뒤 해당 경로를 종료한다.

path와 used가 지키는 불변식

재귀 깊이가 d라면 path에는 길이 d인 접두 순열이 들어 있고, used[i]는 nums[i]가 그 접두사에 포함된 경우에만 참이어야 한다. 이 대응을 선택과 되돌리기 양쪽에서 유지하면 한 원소를 두 번 쓰거나 다음 분기에서 이전 선택을 물려받는 일이 없다.

예를 들어 nums = [1, 2, 3]에서 첫 선택으로 1을 넣으면 다음 위치의 후보는 2, 3이다. [1, 2, 3]을 완성하고 되돌아온 뒤 2의 사용 표시를 해제해야 [1, 3, 2]도 만들 수 있다. 따라서 조합처럼 시작 인덱스만 앞으로 움직이는 대신 매 위치에서 모든 미사용 인덱스를 후보로 살펴본다.

입력 원소가 서로 다르므로 같은 깊이에서 다른 인덱스를 고르면 다른 순열이 된다. 중복 제거 집합은 필요하지 않다.

시간·공간 복잡도

순열은 총 n!개이고, 완성된 순열을 결과에 복사하는 데 O(n) 시간이 필요하다. 그래서 결과 저장을 포함한 시간 복잡도는 O(n × n!)다.

현재 경로와 used 배열, 재귀 호출 스택에 O(n) 공간을 사용한다. 반환되는 n!개의 결과까지 포함한 전체 공간 복잡도는 O(n × n!)다.

3. 문제 해결 코드 (Python)

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        path = []
        used = [False] * len(nums)

        def dfs() -> None:
            if len(path) == len(nums):
                result.append(path.copy())
                return

            for i, num in enumerate(nums):
                if used[i]:
                    continue

                path.append(num)
                used[i] = True
                dfs()
                used[i] = False
                path.pop()

        dfs()
        return result

path는 모든 재귀 호출이 함께 사용하는 작업 리스트이므로 결과에 넣을 때 복사해야 한다. 복사하지 않고 같은 리스트를 저장하면 이후의 pop()과 다음 선택에 의해 이미 완성한 순열도 변경된다.

4. 오답 접근과 반례

사용 여부를 확인하지 않고 모든 원소를 선택하기

각 단계에서 nums의 모든 원소를 무조건 선택하면 같은 원소가 한 순열에 여러 번 들어가고, 반대로 어떤 원소는 빠질 수 있다.

nums = [1, 2]
잘못 생성될 수 있는 경로: [1, 1], [1, 2], [2, 1], [2, 2]
정답: [1, 2], [2, 1]

현재 경로에서 이미 사용한 원소를 제외해야 입력 원소를 정확히 한 번씩 사용하는 조건을 지킬 수 있다.

조합처럼 다음 인덱스부터만 선택하기

start 인덱스를 증가시키며 탐색하면 원소의 순서를 바꿀 수 없다. 예를 들어 [1, 2, 3]에서 첫 번째 원소로 2를 선택하는 경로를 막게 되므로 [2, 1, 3] 같은 순열을 만들지 못한다. 순열에서는 매 깊이마다 전체 원소 중 사용하지 않은 원소를 후보로 확인해야 한다.

완성된 path를 복사하지 않고 저장하기

다음과 같이 같은 리스트 객체를 결과에 추가하면 이후 백트래킹 과정에서 결과가 바뀐다.

result.append(path)  # 잘못된 방식

path의 현재 내용을 보존하려면 result.append(path.copy())처럼 새 리스트를 저장해야 한다.

복사해 실행할 테스트

순열의 반환 순서는 DFS 구현에 따라 달라질 수 있으므로 튜플 집합으로 비교한다.

solver = Solution()
actual = {tuple(items) for items in solver.permute([1, 2, 3])}
expected = {
    (1, 2, 3), (1, 3, 2), (2, 1, 3),
    (2, 3, 1), (3, 1, 2), (3, 2, 1),
}
assert actual == expected
assert solver.permute([1]) == [[1]]

5. 공식 예제와 추가 검증

작성한 permute 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다. 반환 순서는 구현에 따라 달라질 수 있으므로 각 결과를 정렬한 뒤 기대값과 비교했다.

공식 예제

입력 기대 출력 확인 결과
nums = [1,2,3] 6개의 순열 통과
nums = [0,1] [[0,1],[1,0]] 통과
nums = [1] [[1]] 통과

추가 검증 1: 음수와 0을 포함한 입력

입력: nums = [-1, 0, 1]
기대 출력: 6개의 순열
확인 결과: 통과
검증 목적: 원소 값의 부호와 0에 관계없이 위치를 바꾸는지 확인

추가 검증 2: 네 원소의 결과 개수

입력: nums = [1, 2, 3, 4]
기대 출력: 24개의 순열
확인 결과: 통과
검증 목적: 결과 개수가 4!인지 확인

추가 검증 3: 입력 배열 보존

입력: nums = [3, 1, 2]
기대 출력: 6개의 순열
확인 결과: 통과
검증 목적: used 배열과 path를 사용한 풀이가 입력 nums를 변경하지 않는지 확인

6. 다른 풀이 방식 검색 및 비교

인플레이스 교환 방식은 현재 위치에 놓을 원소를 뒤쪽 구간에서 골라 swap하고, 재귀가 끝나면 다시 swap하는 방식이다. 별도의 used 배열이 필요 없고 입력 배열 안에서 상태를 관리한다는 장점이 있다.

이 글에서는 각 원소의 사용 여부가 코드에 직접 드러나는 used 배열 방식을 선택했다. 입력 배열을 건드리지 않고도 상태를 명확히 표현할 수 있으며, path의 길이가 입력 길이가 되면 완성된 순열이라는 종료 조건도 쉽게 확인할 수 있다. 두 방식 모두 결과를 저장하는 공간을 제외하면 O(n) 보조 공간과 O(n × n!) 시간을 사용한다.

마무리

Permutations는 각 위치에 아직 사용하지 않은 원소를 하나씩 배치해 모든 순서를 생성하는 대표적인 백트래킹 문제다. used로 현재 경로의 선택 상태를 기록하고, 재귀가 끝날 때 선택을 되돌리면 원소를 정확히 한 번씩 포함하는 n!개의 순열을 빠짐없이 만들 수 있다.

#백트래킹#LeetCode#난이도 3