13.3 부분 집합 합 문제¶
13.3.1 중복 원소가 없는 경우¶
문제
양의 정수 배열 nums와 목표 양의 정수 target이 주어진다. 원소의 합이 target인 모든 조합을 찾아라. 배열에는 중복 원소가 없고, 각 원소는 여러 번 선택할 수 있다. 조합들을 리스트로 반환하되 중복 조합이 없어야 한다.
예를 들어 입력 집합이 \(\{3, 4, 5\}\)이고 목표 정수가 \(9\)이면 해는 \(\{3, 3, 3\}, \{4, 5\}\)다. 다음 두 가지에 주의하자.
- 입력 집합의 원소는 횟수 제한 없이 반복 선택할 수 있다.
- 부분 집합에서는 원소의 순서를 구분하지 않는다. 예를 들어 \(\{4, 5\}\)와 \(\{5, 4\}\)는 같은 부분 집합이다.
1. 모든 순열 풀이 참고¶
모든 순열 문제처럼 부분 집합을 만드는 과정을 연속된 선택의 결과로 볼 수 있다. 선택할 때마다 '원소의 합'을 갱신하고, 합이 target이 되면 해당 부분 집합을 결과 리스트에 기록한다.
모든 순열 문제와 달리 이 문제에서는 집합의 원소를 횟수 제한 없이 선택할 수 있다. 따라서 선택 여부를 기록하는 불리언 리스트 selected가 필요하지 않다. 모든 순열 코드를 조금 수정하면 다음과 같은 첫 풀이를 얻는다.
subset_sum_i_naive.py
def backtrack(
state: list[int],
target: int,
total: int,
choices: list[int],
res: list[list[int]],
):
"""백트래킹 알고리즘: 부분 집합 합 I"""
# 부분 집합의 합이 target과 같으면 해를 기록한다
if total == target:
res.append(list(state))
return
# 모든 선택지를 순회한다
for i in range(len(choices)):
# 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if total + choices[i] > target:
continue
# 시도: 선택하고 원소의 합 total을 갱신한다
state.append(choices[i])
# 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop()
def subset_sum_i_naive(nums: list[int], target: int) -> list[list[int]]:
"""부분 집합 합 I 풀기(중복 부분 집합 포함)"""
state = [] # 상태(부분 집합)
total = 0 # 부분 집합의 합
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res)
return res
subset_sum_i_naive.cpp
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(vector<int> &state, int target, int total, vector<int> &choices, vector<vector<int>> &res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
res.push_back(state);
return;
}
// 모든 선택지를 순회한다
for (size_t i = 0; i < choices.size(); i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.push_back(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop_back();
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
vector<vector<int>> subsetSumINaive(vector<int> &nums, int target) {
vector<int> state; // 상태(부분 집합)
int total = 0; // 부분 집합의 합
vector<vector<int>> res; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.java
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(List<Integer> state, int target, int total, int[] choices, List<List<Integer>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
res.add(new ArrayList<>(state));
return;
}
// 모든 선택지를 순회한다
for (int i = 0; i < choices.length; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.remove(state.size() - 1);
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
List<List<Integer>> subsetSumINaive(int[] nums, int target) {
List<Integer> state = new ArrayList<>(); // 상태(부분 집합)
int total = 0; // 부분 집합의 합
List<List<Integer>> res = new ArrayList<>(); // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.cs
/* 백트래킹 알고리즘: 부분 집합 합 I */
void Backtrack(List<int> state, int target, int total, int[] choices, List<List<int>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
res.Add(new List<int>(state));
return;
}
// 모든 선택지를 순회한다
for (int i = 0; i < choices.Length; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.Add(choices[i]);
// 다음 선택을 진행한다
Backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.RemoveAt(state.Count - 1);
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
List<List<int>> SubsetSumINaive(int[] nums, int target) {
List<int> state = []; // 상태(부분 집합)
int total = 0; // 부분 집합의 합
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
Backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.go
/* 백트래킹 알고리즘: 부분 집합 합 I */
func backtrackSubsetSumINaive(total, target int, state, choices *[]int, res *[][]int) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == total {
newState := append([]int{}, *state...)
*res = append(*res, newState)
return
}
// 모든 선택지를 순회한다
for i := 0; i < len(*choices); i++ {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if total+(*choices)[i] > target {
continue
}
// 시도: 선택하고 원소의 합 total을 갱신한다
*state = append(*state, (*choices)[i])
// 다음 선택을 진행한다
backtrackSubsetSumINaive(total+(*choices)[i], target, state, choices, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
*state = (*state)[:len(*state)-1]
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
func subsetSumINaive(nums []int, target int) [][]int {
state := make([]int, 0) // 상태(부분 집합)
total := 0 // 부분 집합의 합
res := make([][]int, 0) // 결과 리스트(부분 집합 리스트)
backtrackSubsetSumINaive(total, target, &state, &nums, &res)
return res
}
subset_sum_i_naive.swift
/* 백트래킹 알고리즘: 부분 집합 합 I */
func backtrack(state: inout [Int], target: Int, total: Int, choices: [Int], res: inout [[Int]]) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if total == target {
res.append(state)
return
}
// 모든 선택지를 순회한다
for i in choices.indices {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if total + choices[i] > target {
continue
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.append(choices[i])
// 다음 선택을 진행한다
backtrack(state: &state, target: target, total: total + choices[i], choices: choices, res: &res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast()
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
func subsetSumINaive(nums: [Int], target: Int) -> [[Int]] {
var state: [Int] = [] // 상태(부분 집합)
let total = 0 // 부분 집합의 합
var res: [[Int]] = [] // 결과 리스트(부분 집합 리스트)
backtrack(state: &state, target: target, total: total, choices: nums, res: &res)
return res
}
subset_sum_i_naive.js
/* 백트래킹 알고리즘: 부분 집합 합 I */
function backtrack(state, target, total, choices, res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total === target) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
for (let i = 0; i < choices.length; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
function subsetSumINaive(nums, target) {
const state = []; // 상태(부분 집합)
const total = 0; // 부분 집합의 합
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.ts
/* 백트래킹 알고리즘: 부분 집합 합 I */
function backtrack(
state: number[],
target: number,
total: number,
choices: number[],
res: number[][]
): void {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total === target) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
for (let i = 0; i < choices.length; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
function subsetSumINaive(nums: number[], target: number): number[][] {
const state = []; // 상태(부분 집합)
const total = 0; // 부분 집합의 합
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.dart
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(
List<int> state,
int target,
int total,
List<int> choices,
List<List<int>> res,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
res.add(List.from(state));
return;
}
// 모든 선택지를 순회한다
for (int i = 0; i < choices.length; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast();
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
List<List<int>> subsetSumINaive(List<int> nums, int target) {
List<int> state = []; // 상태(부분 집합)
int total = 0; // 원소의 합
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res);
return res;
}
subset_sum_i_naive.rs
/* 백트래킹 알고리즘: 부분 집합 합 I */
fn backtrack(
state: &mut Vec<i32>,
target: i32,
total: i32,
choices: &[i32],
res: &mut Vec<Vec<i32>>,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if total == target {
res.push(state.clone());
return;
}
// 모든 선택지를 순회한다
for i in 0..choices.len() {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if total + choices[i] > target {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
fn subset_sum_i_naive(nums: &[i32], target: i32) -> Vec<Vec<i32>> {
let mut state = Vec::new(); // 상태(부분 집합)
let total = 0; // 부분 집합의 합
let mut res = Vec::new(); // 결과 리스트(부분 집합 리스트)
backtrack(&mut state, target, total, nums, &mut res);
res
}
subset_sum_i_naive.c
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(int target, int total, int *choices, int choicesSize) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
for (int i = 0; i < stateSize; i++) {
res[resSize][i] = state[i];
}
resColSizes[resSize++] = stateSize;
return;
}
// 모든 선택지를 순회한다
for (int i = 0; i < choicesSize; i++) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue;
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state[stateSize++] = choices[i];
// 다음 선택을 진행한다
backtrack(target, total + choices[i], choices, choicesSize);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
stateSize--;
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
void subsetSumINaive(int *nums, int numsSize, int target) {
resSize = 0; // 해의 개수를 0으로 초기화
backtrack(target, 0, nums, numsSize);
}
subset_sum_i_naive.kt
/* 백트래킹 알고리즘: 부분 집합 합 I */
fun backtrack(
state: MutableList<Int>,
target: Int,
total: Int,
choices: IntArray,
res: MutableList<MutableList<Int>?>
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (total == target) {
res.add(state.toMutableList())
return
}
// 모든 선택지를 순회한다
for (i in choices.indices) {
// 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
if (total + choices[i] > target) {
continue
}
// 시도: 선택하고 원소의 합 total을 갱신한다
state.add(choices[i])
// 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeAt(state.size - 1)
}
}
/* 부분 집합 합 I 풀기(중복 부분 집합 포함) */
fun subsetSumINaive(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
val state = mutableListOf<Int>() // 상태(부분 집합)
val total = 0 // 부분 집합의 합
val res = mutableListOf<MutableList<Int>?>() // 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res)
return res
}
subset_sum_i_naive.rb
### 백트래킹 알고리즘: 부분 집합 합 I ###
def backtrack(state, target, total, choices, res)
# 부분 집합의 합이 target과 같으면 해를 기록한다
if total == target
res << state.dup
return
end
# 모든 선택지를 순회한다
for i in 0...choices.length
# 가지치기: 부분 집합의 합이 target을 초과하면 해당 선택을 건너뛴다
next if total + choices[i] > target
# 시도: 선택하고 원소의 합 total을 갱신한다
state << choices[i]
# 다음 선택을 진행한다
backtrack(state, target, total + choices[i], choices, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop
end
end
### 부분 집합 합 I 풀기(중복 부분 집합 포함)###
def subset_sum_i_naive(nums, target)
state = [] # 상태(부분 집합)
total = 0 # 부분 집합의 합
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, total, nums, res)
res
end
코드 시각화
위 코드에 배열 \([3, 4, 5]\)와 목표 원소 \(9\)를 넣으면 \([3, 3, 3], [4, 5], [5, 4]\)가 나온다. 합이 \(9\)인 모든 부분 집합을 찾았지만 \([4, 5]\)와 \([5, 4]\)는 중복이다.
탐색 과정에서는 선택 순서를 구분하지만 부분 집합에서는 구분하지 않기 때문이다. 아래 그림(13-10)에서 \(4\) 다음 \(5\)를 고르는 것과 \(5\) 다음 \(4\)를 고르는 것은 서로 다른 가지이지만 같은 부분 집합에 대응한다.
그림 13-10 부분 집합 탐색과 범위 초과 가지치기
중복 부분 집합을 제거하는 직접적인 방법은 결과 리스트에서 중복을 제거하는 것이다. 하지만 다음 두 이유로 매우 비효율적이다.
- 배열 원소가 많고 특히
target이 크면 탐색 과정에서 중복 부분 집합이 매우 많이 생긴다. - 부분 집합(배열)이 같은지 비교하는 데 시간이 많이 든다. 먼저 배열을 정렬한 뒤 원소를 하나씩 비교해야 한다.
2. 중복 부분 집합 가지치기¶
탐색 중 가지치기로 중복을 제거해 보자. 아래 그림(13-11)에서 중복 부분 집합은 배열 원소를 서로 다른 순서로 선택할 때 생긴다. 예를 들면 다음과 같다.
- 첫 번째와 두 번째에 각각 \(3\)과 \(4\)를 선택하면 이 두 원소를 포함하는 모든 부분 집합 \([3, 4, \dots]\)가 만들어진다.
- 이후 첫 번째에 \(4\)를 선택하면 두 번째에서는 \(3\)을 건너뛰어야 한다. 이 선택으로 만드는 \([4, 3, \dots]\)는
1.단계에서 만든 부분 집합과 완전히 중복되기 때문이다.
탐색에서 각 레벨의 선택은 왼쪽부터 오른쪽 순서로 시도하므로, 오른쪽으로 갈수록 잘라 내는 가지가 많아진다.
- 첫 두 차례에 \(3\)과 \(5\)를 선택하여 부분 집합 \([3, 5, \dots]\)를 만든다.
- 첫 두 차례에 \(4\)와 \(5\)를 선택하여 부분 집합 \([4, 5, \dots]\)를 만든다.
- 첫 번째에 \(5\)를 선택한다면 두 번째에서는 \(3\)과 \(4\)를 건너뛰어야 한다. \([5, 3, \dots]\)와 \([5, 4, \dots]\)는
1.단계와2.단계의 부분 집합과 완전히 중복되기 때문이다.
그림 13-11 선택 순서의 차이로 생기는 중복 부분 집합
정리하면 입력 배열이 \([x_1, x_2, \dots, x_n]\)일 때 선택 순서 \([x_{i_1}, x_{i_2}, \dots, x_{i_m}]\)는 \(i_1 \leq i_2 \leq \dots \leq i_m\)을 만족해야 한다. 이 조건을 만족하지 않는 선택 순서는 중복을 만들므로 가지치기해야 한다.
3. 코드 구현¶
이 가지치기를 위해 순회 시작점을 나타내는 변수 start를 초기화한다. \(x_{i}\)를 선택한 뒤 다음 차례는 인덱스 \(i\)부터 순회하도록 설정한다. 그러면 선택 순서가 \(i_1 \leq i_2 \leq \dots \leq i_m\)을 만족하여 부분 집합의 유일성을 보장한다.
이 밖에도 다음 두 가지를 최적화했다.
- 탐색을 시작하기 전에 배열
nums를 정렬한다. 선택지를 순회하다가 부분 집합의 합이target을 넘으면 반복문을 바로 종료한다. 뒤의 원소들은 더 크므로 합도 반드시target을 넘기 때문이다. - 원소 합 변수
total을 없애고target에서 값을 빼는 방식으로 합을 추적한다.target이 \(0\)이 되면 해를 기록한다.
subset_sum_i.py
def backtrack(
state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
):
"""백트래킹 알고리즘: 부분 집합 합 I"""
# 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0:
res.append(list(state))
return
# 모든 선택지를 순회한다
# 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for i in range(start, len(choices)):
# 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
# 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0:
break
# 시도: 선택하고 target, start를 갱신한다
state.append(choices[i])
# 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop()
def subset_sum_i(nums: list[int], target: int) -> list[list[int]]:
"""부분 집합 합 I 풀기"""
state = [] # 상태(부분 집합)
nums.sort() # nums를 정렬한다
start = 0 # 순회 시작 위치
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
return res
subset_sum_i.cpp
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.push_back(state);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (int i = start; i < choices.size(); i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.push_back(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop_back();
}
}
/* 부분 집합 합 I 풀기 */
vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
vector<int> state; // 상태(부분 집합)
sort(nums.begin(), nums.end()); // nums를 정렬한다
int start = 0; // 순회 시작 위치
vector<vector<int>> res; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.java
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(new ArrayList<>(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (int i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.remove(state.size() - 1);
}
}
/* 부분 집합 합 I 풀기 */
List<List<Integer>> subsetSumI(int[] nums, int target) {
List<Integer> state = new ArrayList<>(); // 상태(부분 집합)
Arrays.sort(nums); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<Integer>> res = new ArrayList<>(); // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.cs
/* 백트래킹 알고리즘: 부분 집합 합 I */
void Backtrack(List<int> state, int target, int[] choices, int start, List<List<int>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.Add(new List<int>(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (int i = start; i < choices.Length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.Add(choices[i]);
// 다음 선택을 진행한다
Backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.RemoveAt(state.Count - 1);
}
}
/* 부분 집합 합 I 풀기 */
List<List<int>> SubsetSumI(int[] nums, int target) {
List<int> state = []; // 상태(부분 집합)
Array.Sort(nums); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
Backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.go
/* 백트래킹 알고리즘: 부분 집합 합 I */
func backtrackSubsetSumI(start, target int, state, choices *[]int, res *[][]int) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
newState := append([]int{}, *state...)
*res = append(*res, newState)
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for i := start; i < len(*choices); i++ {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target-(*choices)[i] < 0 {
break
}
// 시도: 선택하고 target, start를 갱신한다
*state = append(*state, (*choices)[i])
// 다음 선택을 진행한다
backtrackSubsetSumI(i, target-(*choices)[i], state, choices, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
*state = (*state)[:len(*state)-1]
}
}
/* 부분 집합 합 I 풀기 */
func subsetSumI(nums []int, target int) [][]int {
state := make([]int, 0) // 상태(부분 집합)
sort.Ints(nums) // nums를 정렬한다
start := 0 // 순회 시작 위치
res := make([][]int, 0) // 결과 리스트(부분 집합 리스트)
backtrackSubsetSumI(start, target, &state, &nums, &res)
return res
}
subset_sum_i.swift
/* 백트래킹 알고리즘: 부분 집합 합 I */
func backtrack(state: inout [Int], target: Int, choices: [Int], start: Int, res: inout [[Int]]) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
res.append(state)
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for i in choices.indices.dropFirst(start) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0 {
break
}
// 시도: 선택하고 target, start를 갱신한다
state.append(choices[i])
// 다음 선택을 진행한다
backtrack(state: &state, target: target - choices[i], choices: choices, start: i, res: &res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast()
}
}
/* 부분 집합 합 I 풀기 */
func subsetSumI(nums: [Int], target: Int) -> [[Int]] {
var state: [Int] = [] // 상태(부분 집합)
let nums = nums.sorted() // nums를 정렬한다
let start = 0 // 순회 시작 위치
var res: [[Int]] = [] // 결과 리스트(부분 집합 리스트)
backtrack(state: &state, target: target, choices: nums, start: start, res: &res)
return res
}
subset_sum_i.js
/* 백트래킹 알고리즘: 부분 집합 합 I */
function backtrack(state, target, choices, start, res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target === 0) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (let i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기 */
function subsetSumI(nums, target) {
const state = []; // 상태(부분 집합)
nums.sort((a, b) => a - b); // nums를 정렬한다
const start = 0; // 순회 시작 위치
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.ts
/* 백트래킹 알고리즘: 부분 집합 합 I */
function backtrack(
state: number[],
target: number,
choices: number[],
start: number,
res: number[][]
): void {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target === 0) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (let i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기 */
function subsetSumI(nums: number[], target: number): number[][] {
const state = []; // 상태(부분 집합)
nums.sort((a, b) => a - b); // nums를 정렬한다
const start = 0; // 순회 시작 위치
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.dart
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(
List<int> state,
int target,
List<int> choices,
int start,
List<List<int>> res,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(List.from(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (int i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast();
}
}
/* 부분 집합 합 I 풀기 */
List<List<int>> subsetSumI(List<int> nums, int target) {
List<int> state = []; // 상태(부분 집합)
nums.sort(); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_i.rs
/* 백트래킹 알고리즘: 부분 집합 합 I */
fn backtrack(
state: &mut Vec<i32>,
target: i32,
choices: &[i32],
start: usize,
res: &mut Vec<Vec<i32>>,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
res.push(state.clone());
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for i in start..choices.len() {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0 {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 I 풀기 */
fn subset_sum_i(nums: &mut [i32], target: i32) -> Vec<Vec<i32>> {
let mut state = Vec::new(); // 상태(부분 집합)
nums.sort(); // nums를 정렬한다
let start = 0; // 순회 시작 위치
let mut res = Vec::new(); // 결과 리스트(부분 집합 리스트)
backtrack(&mut state, target, nums, start, &mut res);
res
}
subset_sum_i.c
/* 백트래킹 알고리즘: 부분 집합 합 I */
void backtrack(int target, int *choices, int choicesSize, int start) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
for (int i = 0; i < stateSize; ++i) {
res[resSize][i] = state[i];
}
resColSizes[resSize++] = stateSize;
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (int i = start; i < choicesSize; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 시도: 선택하고 target, start를 갱신한다
state[stateSize] = choices[i];
stateSize++;
// 다음 선택을 진행한다
backtrack(target - choices[i], choices, choicesSize, i);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
stateSize--;
}
}
/* 부분 집합 합 I 풀기 */
void subsetSumI(int *nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), cmp); // nums를 정렬한다
int start = 0; // 순회 시작 위치
backtrack(target, nums, numsSize, start);
}
subset_sum_i.kt
/* 백트래킹 알고리즘: 부분 집합 합 I */
fun backtrack(
state: MutableList<Int>,
target: Int,
choices: IntArray,
start: Int,
res: MutableList<MutableList<Int>?>
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(state.toMutableList())
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for (i in start..<choices.size) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i])
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeAt(state.size - 1)
}
}
/* 부분 집합 합 I 풀기 */
fun subsetSumI(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
val state = mutableListOf<Int>() // 상태(부분 집합)
nums.sort() // nums를 정렬한다
val start = 0 // 순회 시작 위치
val res = mutableListOf<MutableList<Int>?>() // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
return res
}
subset_sum_i.rb
### 백트래킹 알고리즘: 부분 집합 합 I ###
def backtrack(state, target, choices, start, res)
# 부분 집합의 합이 target과 같으면 해를 기록한다
if target.zero?
res << state.dup
return
end
# 모든 선택지를 순회한다
# 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
for i in start...choices.length
# 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
# 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
break if target - choices[i] < 0
# 시도: 선택하고 target, start를 갱신한다
state << choices[i]
# 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop
end
end
### 부분 집합 합 I 풀기 ###
def subset_sum_i(nums, target)
state = [] # 상태(부분 집합)
nums.sort! # nums를 정렬한다
start = 0 # 순회 시작 위치
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
res
end
코드 시각화
아래 그림(13-12)은 배열 \([3, 4, 5]\)와 목표 원소 \(9\)를 위 코드에 넣었을 때의 전체 백트래킹 과정이다.
그림 13-12 부분 집합 합 I의 백트래킹 과정
13.3.2 중복 원소가 있는 경우¶
문제
양의 정수 배열 nums와 목표 양의 정수 target이 주어진다. 원소의 합이 target인 모든 조합을 찾아라. 배열에는 중복 원소가 있을 수 있고, 각 원소는 한 번만 선택할 수 있다. 조합들을 리스트로 반환하되 중복 조합이 없어야 한다.
앞 문제와 달리 입력 배열에 중복 원소가 있을 수 있어 새로운 문제가 생긴다. 예를 들어 배열 \([4, \hat{4}, 5]\)와 목표 원소 \(9\)를 기존 코드에 넣으면 \([4, 5], [\hat{4}, 5]\)가 나와 부분 집합이 중복된다.
중복의 원인은 값이 같은 원소를 한 차례의 선택에서 여러 번 고르기 때문이다. 아래 그림(13-13)에서 첫 차례의 세 선택지 중 두 개가 \(4\)여서 중복된 두 탐색 가지가 만들어지고, 같은 부분 집합을 출력한다. 마찬가지로 두 번째 차례의 두 \(4\)도 중복을 만든다.
그림 13-13 같은 값의 원소로 생기는 중복 부분 집합
1. 같은 값의 원소 가지치기¶
이를 해결하려면 각 차례에서 같은 값의 원소를 한 번만 선택하도록 제한해야 한다. 구현 방법은 간단하면서도 기발하다. 배열이 정렬되어 있으므로 같은 원소끼리는 인접한다. 따라서 한 차례의 선택에서 현재 원소가 왼쪽 원소와 같다면 이미 선택한 값이라는 뜻이므로 바로 건너뛴다.
또한 이 문제에서는 각 배열 원소를 한 번만 선택할 수 있다. 다행히 start로 이 제약도 만족시킬 수 있다. \(x_{i}\)를 선택한 뒤 다음 차례는 인덱스 \(i + 1\)부터 배열의 끝을 향해 순회하도록 설정한다. 그러면 중복 부분 집합과 같은 원소의 반복 선택을 모두 막을 수 있다.
2. 코드 구현¶
subset_sum_ii.py
def backtrack(
state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
):
"""백트래킹 알고리즘: 부분 집합 합 II"""
# 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0:
res.append(list(state))
return
# 모든 선택지를 순회한다
# 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
# 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for i in range(start, len(choices)):
# 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
# 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0:
break
# 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if i > start and choices[i] == choices[i - 1]:
continue
# 시도: 선택하고 target, start를 갱신한다
state.append(choices[i])
# 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop()
def subset_sum_ii(nums: list[int], target: int) -> list[list[int]]:
"""부분 집합 합 II 풀기"""
state = [] # 상태(부분 집합)
nums.sort() # nums를 정렬한다
start = 0 # 순회 시작 위치
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
return res
subset_sum_ii.cpp
/* 백트래킹 알고리즘: 부분 집합 합 II */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.push_back(state);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (int i = start; i < choices.size(); i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.push_back(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop_back();
}
}
/* 부분 집합 합 II 풀기 */
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
vector<int> state; // 상태(부분 집합)
sort(nums.begin(), nums.end()); // nums를 정렬한다
int start = 0; // 순회 시작 위치
vector<vector<int>> res; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.java
/* 백트래킹 알고리즘: 부분 집합 합 II */
void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(new ArrayList<>(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (int i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.remove(state.size() - 1);
}
}
/* 부분 집합 합 II 풀기 */
List<List<Integer>> subsetSumII(int[] nums, int target) {
List<Integer> state = new ArrayList<>(); // 상태(부분 집합)
Arrays.sort(nums); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<Integer>> res = new ArrayList<>(); // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.cs
/* 백트래킹 알고리즘: 부분 집합 합 II */
void Backtrack(List<int> state, int target, int[] choices, int start, List<List<int>> res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.Add(new List<int>(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (int i = start; i < choices.Length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.Add(choices[i]);
// 다음 선택을 진행한다
Backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.RemoveAt(state.Count - 1);
}
}
/* 부분 집합 합 II 풀기 */
List<List<int>> SubsetSumII(int[] nums, int target) {
List<int> state = []; // 상태(부분 집합)
Array.Sort(nums); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
Backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.go
/* 백트래킹 알고리즘: 부분 집합 합 II */
func backtrackSubsetSumII(start, target int, state, choices *[]int, res *[][]int) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
newState := append([]int{}, *state...)
*res = append(*res, newState)
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for i := start; i < len(*choices); i++ {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target-(*choices)[i] < 0 {
break
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if i > start && (*choices)[i] == (*choices)[i-1] {
continue
}
// 시도: 선택하고 target, start를 갱신한다
*state = append(*state, (*choices)[i])
// 다음 선택을 진행한다
backtrackSubsetSumII(i+1, target-(*choices)[i], state, choices, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
*state = (*state)[:len(*state)-1]
}
}
/* 부분 집합 합 II 풀기 */
func subsetSumII(nums []int, target int) [][]int {
state := make([]int, 0) // 상태(부분 집합)
sort.Ints(nums) // nums를 정렬한다
start := 0 // 순회 시작 위치
res := make([][]int, 0) // 결과 리스트(부분 집합 리스트)
backtrackSubsetSumII(start, target, &state, &nums, &res)
return res
}
subset_sum_ii.swift
/* 백트래킹 알고리즘: 부분 집합 합 II */
func backtrack(state: inout [Int], target: Int, choices: [Int], start: Int, res: inout [[Int]]) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
res.append(state)
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for i in choices.indices.dropFirst(start) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0 {
break
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if i > start, choices[i] == choices[i - 1] {
continue
}
// 시도: 선택하고 target, start를 갱신한다
state.append(choices[i])
// 다음 선택을 진행한다
backtrack(state: &state, target: target - choices[i], choices: choices, start: i + 1, res: &res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast()
}
}
/* 부분 집합 합 II 풀기 */
func subsetSumII(nums: [Int], target: Int) -> [[Int]] {
var state: [Int] = [] // 상태(부분 집합)
let nums = nums.sorted() // nums를 정렬한다
let start = 0 // 순회 시작 위치
var res: [[Int]] = [] // 결과 리스트(부분 집합 리스트)
backtrack(state: &state, target: target, choices: nums, start: start, res: &res)
return res
}
subset_sum_ii.js
/* 백트래킹 알고리즘: 부분 집합 합 II */
function backtrack(state, target, choices, start, res) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target === 0) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (let i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] === choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 II 풀기 */
function subsetSumII(nums, target) {
const state = []; // 상태(부분 집합)
nums.sort((a, b) => a - b); // nums를 정렬한다
const start = 0; // 순회 시작 위치
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.ts
/* 백트래킹 알고리즘: 부분 집합 합 II */
function backtrack(
state: number[],
target: number,
choices: number[],
start: number,
res: number[][]
): void {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target === 0) {
res.push([...state]);
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (let i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] === choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 II 풀기 */
function subsetSumII(nums: number[], target: number): number[][] {
const state = []; // 상태(부분 집합)
nums.sort((a, b) => a - b); // nums를 정렬한다
const start = 0; // 순회 시작 위치
const res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.dart
/* 백트래킹 알고리즘: 부분 집합 합 II */
void backtrack(
List<int> state,
int target,
List<int> choices,
int start,
List<List<int>> res,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(List.from(state));
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (int i = start; i < choices.length; i++) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeLast();
}
}
/* 부분 집합 합 II 풀기 */
List<List<int>> subsetSumII(List<int> nums, int target) {
List<int> state = []; // 상태(부분 집합)
nums.sort(); // nums를 정렬한다
int start = 0; // 순회 시작 위치
List<List<int>> res = []; // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res);
return res;
}
subset_sum_ii.rs
/* 백트래킹 알고리즘: 부분 집합 합 II */
fn backtrack(
state: &mut Vec<i32>,
target: i32,
choices: &[i32],
start: usize,
res: &mut Vec<Vec<i32>>,
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if target == 0 {
res.push(state.clone());
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for i in start..choices.len() {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if target - choices[i] < 0 {
break;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if i > start && choices[i] == choices[i - 1] {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state.push(choices[i]);
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop();
}
}
/* 부분 집합 합 II 풀기 */
fn subset_sum_ii(nums: &mut [i32], target: i32) -> Vec<Vec<i32>> {
let mut state = Vec::new(); // 상태(부분 집합)
nums.sort(); // nums를 정렬한다
let start = 0; // 순회 시작 위치
let mut res = Vec::new(); // 결과 리스트(부분 집합 리스트)
backtrack(&mut state, target, nums, start, &mut res);
res
}
subset_sum_ii.c
/* 백트래킹 알고리즘: 부분 집합 합 II */
void backtrack(int target, int *choices, int choicesSize, int start) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
for (int i = 0; i < stateSize; i++) {
res[resSize][i] = state[i];
}
resColSizes[resSize++] = stateSize;
return;
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (int i = start; i < choicesSize; i++) {
// 가지치기 1: 부분 집합의 합이 target을 넘으면 바로 건너뛴다
if (target - choices[i] < 0) {
continue;
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue;
}
// 시도: 선택하고 target, start를 갱신한다
state[stateSize] = choices[i];
stateSize++;
// 다음 선택을 진행한다
backtrack(target - choices[i], choices, choicesSize, i + 1);
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
stateSize--;
}
}
/* 부분 집합 합 II 풀기 */
void subsetSumII(int *nums, int numsSize, int target) {
// nums를 정렬한다
qsort(nums, numsSize, sizeof(int), cmp);
// 백트래킹 시작
backtrack(target, nums, numsSize, 0);
}
subset_sum_ii.kt
/* 백트래킹 알고리즘: 부분 집합 합 II */
fun backtrack(
state: MutableList<Int>,
target: Int,
choices: IntArray,
start: Int,
res: MutableList<MutableList<Int>?>
) {
// 부분 집합의 합이 target과 같으면 해를 기록한다
if (target == 0) {
res.add(state.toMutableList())
return
}
// 모든 선택지를 순회한다
// 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
// 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for (i in start..<choices.size) {
// 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
// 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
if (target - choices[i] < 0) {
break
}
// 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
if (i > start && choices[i] == choices[i - 1]) {
continue
}
// 시도: 선택하고 target, start를 갱신한다
state.add(choices[i])
// 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res)
// 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.removeAt(state.size - 1)
}
}
/* 부분 집합 합 II 풀기 */
fun subsetSumII(nums: IntArray, target: Int): MutableList<MutableList<Int>?> {
val state = mutableListOf<Int>() // 상태(부분 집합)
nums.sort() // nums를 정렬한다
val start = 0 // 순회 시작 위치
val res = mutableListOf<MutableList<Int>?>() // 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
return res
}
subset_sum_ii.rb
### 백트래킹 알고리즘: 부분 집합 합 II ###
def backtrack(state, target, choices, start, res)
# 부분 집합의 합이 target과 같으면 해를 기록한다
if target.zero?
res << state.dup
return
end
# 모든 선택지를 순회한다
# 가지치기 2: start부터 순회하여 중복 부분 집합 생성을 방지한다
# 가지치기 3: start부터 순회하여 같은 원소의 중복 선택을 방지한다
for i in start...choices.length
# 가지치기 1: 부분 집합의 합이 target을 초과하면 즉시 반복문을 종료한다
# 배열이 정렬되어 있어 뒤의 원소가 더 크므로, 부분 집합의 합이 반드시 target을 초과하기 때문이다
break if target - choices[i] < 0
# 가지치기 4: 해당 원소가 왼쪽 원소와 같으면 탐색 분기가 중복되므로 바로 건너뛴다
next if i > start && choices[i] == choices[i - 1]
# 시도: 선택하고 target, start를 갱신한다
state << choices[i]
# 다음 선택을 진행한다
backtrack(state, target - choices[i], choices, i + 1, res)
# 되돌리기: 선택을 취소하고 이전 상태로 되돌린다
state.pop
end
end
### 부분 집합 합 II 풀기 ###
def subset_sum_ii(nums, target)
state = [] # 상태(부분 집합)
nums.sort! # nums를 정렬한다
start = 0 # 순회 시작 위치
res = [] # 결과 리스트(부분 집합 리스트)
backtrack(state, target, nums, start, res)
res
end
코드 시각화
아래 그림(13-14)은 배열 \([4, 4, 5]\)와 목표 원소 \(9\)의 백트래킹 과정으로, 네 가지 가지치기를 포함한다. 그림과 코드 주석을 함께 보면서 전체 탐색 과정과 각 가지치기가 어떻게 작동하는지 이해해 보자.
그림 13-14 부분 집합 합 II의 백트래킹 과정