# 연습 문제

## 개념 확인

### 이 순열 알고리즘은 결과를 빠뜨리는가

한 백트래킹 알고리즘이 `1, 2, 3` 순서로 숫자를 시도하며 모든 순열을 생성한다. 숫자 `x`를 선택할 때마다 다음을 수행한다.

1. 현재 경로의 끝에 `x`를 추가한다.
2. `x`를 ‘사용함’으로 표시한다.
3. 재귀 호출로 다음 위치를 채운다.

재귀 호출이 반환된 뒤, 학생은 경로 끝의 `x`만 삭제하고 다음 숫자를 계속 시도했다.

<!-- numbered-subquestions -->

1. 알고리즘이 처음 얻는 순열은 무엇인가? 순열 6개를 모두 얻을 수 있는가?
2. 재귀 호출에서 이전 단계로 돌아가기 전에 경로 끝의 숫자를 삭제하는 것만으로 충분한가? 충분하지 않다면 무엇을 더 해야 하는지 이유와 함께 설명하라.

??? success "참고 답안"

    1. 처음 얻는 순열은 `[1, 2, 3]`이지만, 모든 순열을 얻을 수는 없다. 반환하면서 경로는 짧아져도
        숫자 1, 2, 3은 여전히 모두 ‘사용함’으로 표시되어 있어 이후 분기에서 선택할 숫자가 없기 때문이다.

    2. 충분하지 않다. 경로 끝의 `x`를 삭제한 뒤에는 `x`를 다시 ‘사용하지 않음’으로 표시해야 한다.
        현재 경로와 사용 여부 표시가 함께 탐색 상태를 나타낸다. 선택할 때 두 곳을 수정했으므로 되돌아갈 때도 두 곳을 모두 복원해야
        다른 분기에서 `x`를 다시 선택할 수 있다.

### 숫자를 선택하는 순서가 중요한가

정렬된 배열 `[2, 3, 5]`와 목표 값 5가 주어지며, 각 숫자는 반복해서 선택할 수 있다.
알고리즘에서는 각 탐색 경로의 숫자가 작은 것부터 큰 것 순으로만 나타나도록 제한한다.

<!-- numbered-subquestions -->

1. 서로 다른 어떤 조합을 얻을 수 있는가?
2. 같은 숫자들을 다른 순서로 반복해서 탐색할 필요가 없는 이유는 무엇인가? ‘작은 것부터 큰 것 순’이라는 제한은 어떤 역할을 하는가?
3. 현재 경로가 `[3]`이고 2가 더 필요한 상황에서 다음 후보 숫자가 3이다. 이때 이 단계의 나머지 후보를 모두 확인하지 않고 멈출 수 있는 이유는 무엇인가?

??? success "참고 답안"

    1. 서로 다른 조합은 `[2, 3]`과 `[5]`다.

    2. 이 문제에서는 `[2, 3]`과 `[3, 2]`를 같은 조합으로 취급하므로 숫자를 선택하는 순서는 답에 반영하지 않는다.
        경로의 숫자가 작은 것부터 큰 것 순으로 나타나도록 정하면 탐색 중에 `[3, 2]` 같은 중복 조합을 바로 건너뛸 수 있다.

    3. 현재 2가 더 필요한데 후보 숫자 3은 이미 2보다 크다. 배열이 정렬되어 있으므로
        3 뒤의 후보는 더 크기만 할 뿐이고, 모두 현재 조합에 추가할 수 없다. 따라서 이 단계의 확인을 바로 끝낼 수 있다.

### 다음 퀸은 어디에 놓을 수 있는가

`4 × 4` 체스판에 행별로 퀸을 놓으며, 행과 열의 인덱스는 모두 0부터 시작한다.
현재 `(0, 1)`과 `(1, 3)`에 퀸을 놓았고, 이제 인덱스 2인 행에 다음 퀸을 놓으려 한다.

<!-- numbered-subquestions -->

1. ‘같은 열’이라는 이유로 제외되는 열은 어디인가?
2. 남은 열 가운데 ‘같은 대각선’이라는 이유로 제외되는 위치는 어디인가?
3. 인덱스 2인 행에서 시도해 볼 수 있는 위치는 어디인가?

??? success "참고 답안"

    1. 인덱스 1과 3인 열에 이미 퀸이 있으므로 `(2, 1)`과 `(2, 3)`은 제외된다.

    2. 남은 위치 중 `(2, 2)`는 `(1, 3)`과 같은 대각선에 있으므로 역시 제외된다.
        `(2, 0)`은 이미 놓인 두 퀸 중 어느 것과도 같은 열이나 같은 대각선에 있지 않다.

    3. 인덱스 2인 행에서 시도할 수 있는 위치는 `(2, 0)`뿐이다.

        이 단계에서는 현재 배치가 조건에 맞는다는 것만 확인한 셈이다. 이후 체스판을 완성할 수 없다면 여전히 되돌아가 더 앞 단계의 다른 선택을 시도해야 한다.

## 프로그래밍 연습

### 중복 원소가 없는 모든 순열

정수 배열 `nums`에는 원소가 적어도 하나 있으며, 모든 원소가 서로 다르다.
각 원소를 한 번씩 사용하여 만들 수 있는 모든 순서를 나열하고, 각 순서를 배열로 반환하라.
결과에서 순열들이 나오는 순서는 상관없다.
백트래킹을 사용하고, 각 위치의 원소가 현재 순열에 이미 선택되었는지 불리언 배열로 기록하라.

??? tip "풀이 힌트"

    1. 재귀 깊이는 순열의 몇 번째 위치를 채우는 중인지를 나타낸다.
    2. 각 단계에서는 아직 사용하지 않은 원소만 시도한다.
    3. 경로 길이가 `nums`의 길이에 도달하면 경로의 복사본을 답에 추가한다.

[LeetCode](https://leetcode.com/problems/permutations/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }