완전 탐색 - 모든 경우를 빠짐없이

이 장에서 배우는 것

앞 장에서 정해진 규칙에 따라 상태를 바꾸었다면, 이번에는 가능한 선택을 모두 만들어 답을 찾는다. 배달 순서가 여러 가지라면 순서마다 비용을 계산하고, 물품을 골라야 한다면 가능한 묶음을 하나씩 검사한다. 이런 풀이를 완전 탐색(exhaustive search)이라 한다. 핵심은 반복문을 많이 쓰는 데 있지 않다. 무엇을 하나의 후보로 볼지 정하고, 후보를 빠뜨리거나 잘못 중복시키지 않는 데 있다.

완전 탐색은 입력이 작을 때 그 자체로 실용적인 풀이가 된다. 입력이 커서 그대로 사용할 수 없더라도, 작은 입력에서 다른 풀이를 검사하는 기준으로 쓸 수 있다. 여기서는 후보의 구조를 먼저 손으로 확인한 다음, 같은 후보를 서로 다른 방법으로 만들어 결과를 대조한다.

• 선택 순서와 중복 허용 여부를 구분해 반복문의 범위를 정한다.
• 순열·조합·부분집합을 표준 라이브러리와 반복문으로 만든다.
• 정수의 각 자리를 선택 여부로 사용하는 비트마스크를 이해한다.
• 완전 탐색의 정확성과 비용을 설명하고, 작은 입력을 전수 검사한다.
• 가지치기를 적용하기 전에 갖추어야 할 기준 풀이의 역할을 이해한다.

문제 상황

작은 작업장의 운영 도구를 만든다고 하자. 첫째, 담당자는 방문 후보 세 곳 중 서로 다른 두 곳을 골라 차례대로 방문한다. 둘째, 체험 행사에 진열할 소품 네 개 중 두 개를 고른다. 셋째, 재고 조정 기록 중 일부를 묶어 지정한 합을 만드는지 확인한다. 세 작업은 모두 고르는 문제지만, 같은 반복문을 그대로 적용할 수는 없다.

방문 계획에서는 첫 방문지와 둘째 방문지가 바뀌면 다른 계획이다. 소품 묶음에서는 같은 두 소품의 나열 순서가 달라도 같은 묶음이다. 재고 기록에서는 고르는 개수부터 정해져 있지 않다. 이 차이를 놓치면 필요한 후보를 빠뜨리거나 같은 후보를 여러 번 세게 된다.

재고 조정 기록은 증가량과 감소량을 함께 담는다. 예시 기록은 [2, -1, 3, 2]이고 목표 합은 4다. 기록은 발생 위치로 구분한다. 맨 앞의 2와 맨 뒤의 2는 값이 같아도 서로 다른 기록이다. 결과는 선택한 기록의 인덱스를 오름차순으로 담은 튜플로 나타낸다. 같은 기록을 두 번 고를 수는 없다.

실제 도구에서도 먼저 이런 작은 사례를 정확하게 처리해야 한다. 결과 개수만 맞는 것으로는 충분하지 않다. 다른 기록을 선택했는데 값이 같다는 이유로 하나로 합치거나, 빈 선택을 빼먹으면 이후 검증도 잘못된 기준에 의존하게 된다.

후보의 모양부터 정한다

방문 순서는 순열이다

방문 후보를 A, B, C라고 하자. 서로 다른 두 곳을 순서 있게 고르면 (A, B)와 (B, A)는 다른 후보다. 이렇게 순서를 구분하는 선택을 순열(permutation)이라 한다. 첫 방문지는 세 가지이고, 각 경우의 둘째 방문지는 이미 고른 곳을 제외한 두 가지다. 따라서 후보는 여섯 개다.

첫 방문지를 고정한 뒤 둘째 방문지를 모두 확인한다

첫 방문지	검사할 둘째 방문지	남는 후보
A	A, B, C	(A, B), (A, C)
B	A, B, C	(B, A), (B, C)
C	A, B, C	(C, A), (C, B)

직접 구현할 때는 바깥 반복문이 첫 위치를, 안쪽 반복문이 둘째 위치를 맡는다. 다음 코드는 가능한 인덱스 쌍을 모두 방문한 뒤 같은 장소를 두 번 고른 경우만 제외한다.

places = ["A", "B", "C"]
routes = []
for i in range(len(places)):
    for j in range(len(places)):
        if i != j:
            routes.append((places[i], places[j]))

바깥 반복문의 한 차례가 끝나면 해당 첫 방문지에 연결되는 유효한 둘째 방문지를 모두 검사했다. 모든 첫 방문지에 대해 이를 반복하므로 가능한 계획이 빠지지 않는다. 한 계획의 첫째·둘째 인덱스는 각각 하나로 정해지므로 같은 계획을 두 번 추가하지도 않는다.

후보 수가 n이면 위 코드는 조건 검사까지 포함해 n²번 반복한다. 시간 복잡도는 O(n²)이고, 결과를 모두 저장하는 공간도 O(n²)이다. 표준 라이브러리에서는 itertools.permutations(places, 2)로 같은 선택 구조를 표현할 수 있다.

진열 소품 묶음은 조합이다

소품 네 개 중 두 개를 고르되 진열 순서를 구분하지 않는다면 조합(combination)이 알맞다. 인덱스가 0, 1인 묶음을 만든 뒤 1, 0을 다시 만들 필요가 없다. 처음부터 i < j인 쌍만 만들면 된다.

items = ["컵", "접시", "수저", "쟁반"]
pairs = []
for i in range(len(items)):
    for j in range(i + 1, len(items)):
        pairs.append((items[i], items[j]))

서로 다른 두 인덱스에는 작은 쪽과 큰 쪽이 하나씩 있다. 따라서 작은 쪽을 i, 큰 쪽을 j로 두면 모든 묶음을 정확히 한 번 만들 수 있다. 이처럼 나열 규칙을 정해 중복 표현을 없애면, 만든 뒤 중복을 제거하는 작업이 필요하지 않다.

후보 수는 n(n-1)/2이고 시간과 결과 저장 공간은 모두 O(n²)이다. itertools.combinations(items, 2)도 이 선택에 해당한다. 라이브러리 함수는 결과를 차례로 내놓는 반복자를 반환한다. 즉시 리스트로 바꾸지 않고 하나씩 검사하면 결과 전체를 보관할 필요가 없다.

고르는 개수 r가 달라질 때는 반복문을 계속 늘려 쓰기 어렵다. 직접 구현하는 한 방법은 길이가 짧은 후보 목록에서 다음 길이의 후보 목록을 만드는 것이다. 다음 코드는 값 대신 인덱스를 다룬다. 순열은 이미 사용한 인덱스를 제외하고, 조합은 마지막 인덱스보다 큰 인덱스만 붙인다.

def permutation_indices(n, r):
    paths = [()]
    for _ in range(r):
        next_paths = []
        for path in paths:
            for i in range(n):
                if i not in path:
                    next_paths.append(path + (i,))
        paths = next_paths
    return paths


def combination_indices(n, r):
    paths = [()]
    for _ in range(r):
        next_paths = []
        for path in paths:
            start = path[-1] + 1 if path else 0
            for i in range(start, n):
                next_paths.append(path + (i,))
        paths = next_paths
    return paths

두 함수는 0 ≤ r ≤ n인 입력을 가정한다. 매 단계가 끝났을 때 paths에는 그 길이의 유효한 후보가 모두 들어 있다. 길이 0의 후보는 빈 튜플 하나다. 유효한 다음 후보에서 마지막 원소를 떼면 반드시 이전 단계의 후보가 되므로, 다음 단계도 빠짐없이 만들어진다.

순열의 최종 후보 수를 P, 조합의 최종 후보 수를 C라고 하자. 튜플 복사와 포함 검사를 고려한 느슨한 시간 상한은 각각 O(nr²P), O(nr²C)이다. 최종 결과만 보관해도 각각 O(rP), O(rC) 공간이 필요하다. 중간 후보를 모두 담는 방식은 원리를 보기 쉽지만, 결과를 하나씩 내놓는 방식보다 메모리를 많이 쓸 수 있다. r=0에서는 두 함수 모두 빈 튜플 하나를 반환한다.

부분집합을 세 가지 방법으로 만든다

각 기록을 넣거나 넣지 않는다

부분집합(subset)은 원소를 몇 개 고를지 정하지 않은 선택이다. 각 인덱스마다 선택하지 않거나 선택하는 두 경우가 있다. 원소가 n개이면 후보는 2ⁿ개다. 아무것도 고르지 않는 빈 부분집합과 전부 고르는 부분집합도 여기에 포함된다.

직접 구현할 때는 빈 튜플 하나에서 출발한다. 새 인덱스를 만날 때마다 기존 후보는 그대로 남기고, 각 기존 후보에 새 인덱스를 붙인 후보를 추가한다. 기존 후보를 순회하는 동안 같은 리스트에 계속 추가하면 안 된다. 별도의 목록을 완성한 뒤 합친다.

새 인덱스를 처리할 때 기존 후보 수가 두 배가 된다

처리한 인덱스	기존 후보	새로 추가하는 후보	처리 후 개수
없음	()	없음	1
0	()	(0,)	2
1	(), (0,)	(1,), (0, 1)	4
2	(), (0,), (1,), (0, 1)	(2,), (0, 2), (1, 2), (0, 1, 2)	8

인덱스 i를 처리하기 직전, 목록에는 0부터 i-1까지로 만든 부분집합이 정확히 한 번씩 있다고 하자. 다음 부분집합은 i를 포함하지 않는 것과 포함하는 것으로 나뉜다. 앞쪽은 기존 목록이고 뒤쪽은 새로 붙인 목록이다. 두 목록은 i의 포함 여부가 달라 겹치지 않는다. 이 성질이 반복 내내 유지되는 불변식이다.

크기별 조합을 합친다

부분집합을 크기에 따라 나누어도 된다. 크기 0의 조합, 크기 1의 조합, 그리고 크기 n의 조합까지 모두 검사한다. 모든 부분집합에는 크기가 하나로 정해져 있으므로 서로 다른 크기의 묶음 사이에는 중복이 없다. 각 크기의 조합이 빠짐없이 만들어지면 전체 부분집합도 빠짐없이 만들어진다.

완성 코드에서는 combinations(range(n), r)를 사용한다. 값의 목록이 아니라 인덱스의 목록을 넘긴다는 점이 중요하다. 값이 같은 두 기록도 별개의 원소로 유지해야 하기 때문이다. 크기 0의 조합은 빈 튜플 하나이며, 그 합은 0이다.

비트마스크로 선택을 표시한다

비트마스크(bitmask)는 정수의 이진 표현을 선택표로 사용하는 방법이다. 이진수의 각 자리인 비트가 1이면 해당 인덱스를 선택하고 0이면 선택하지 않는다. 1 << i는 인덱스 i에 대응하는 자리만 1인 정수다. mask & (1 << i)가 0이 아니면 그 자리가 켜져 있다.

네 기록을 예로 들면 정수 9는 이진수 1001이므로 인덱스 0과 3을 선택한다. 이진수는 오른쪽 끝부터 인덱스 0에 대응한다. 보이는 문자열의 왼쪽 끝을 인덱스 0으로 읽지 않도록 주의한다.

range(1 << n)은 0부터 2ⁿ-1까지의 정수를 만든다. 이 범위의 각 정수는 정확히 하나의 선택표에 대응한다. 반대로 모든 선택표는 이 범위 안의 정수 하나로 표현된다. 따라서 정수를 모두 훑으면 부분집합도 정확히 한 번씩 검사한다.

세 방법은 후보를 만드는 순서가 다르다. 직접 구현은 새 원소의 처리 순서를 따르고, 조합은 크기순으로 만들며, 비트마스크는 정수의 크기순으로 만든다. 결과를 비교할 때는 각 후보의 표현을 인덱스 튜플로 통일하고 결과 목록을 정렬한다. 후보 생성 순서가 다르다는 이유로 오답으로 판단해서는 안 된다.

모두 확인한 결과를 기준으로 삼는다

부분집합 합 문제의 판정은 간단하다. 선택한 인덱스의 값을 더해 목표와 같은지 검사한다. 어려운 부분은 후보를 빠짐없이 만드는 일과 입력 크기를 감당할 수 있는지 확인하는 일이다. 후보마다 최대 n개 값을 확인하면 생성과 합 계산에 O(n2ⁿ) 시간이 든다.

완성 코드는 비교를 위해 정답 목록도 정렬한다. 정답 수를 K라고 하면 튜플 비교까지 고려한 정렬의 보수적인 시간 상한은 O(nK log(K+1))이다. 따라서 정렬을 포함한 전체 시간은 O(n2ⁿ + nK log(K+1))으로 설명할 수 있다. 존재 여부만 찾는 문제라면 정답 목록과 정렬 자체가 필요하지 않다.

직접 구현은 모든 부분집합 튜플을 저장하므로 결과를 제외해도 O(n2ⁿ) 공간을 쓴다. 조합과 비트마스크 방식은 후보 하나를 검사할 때 O(n) 작업 공간이면 된다. 다만 이 프로그램은 정답 자체를 전부 반환하므로 세 방법 모두 최대 O(nK)의 결과 공간이 추가된다. 여기서 비트 연산 비용은 탐색 가능한 작은 n의 범위에서 단순화해 계산한다.

입력이 하나 늘 때 후보가 두 배가 된다는 점이 실제 제한을 결정한다. 원소 10개의 후보는 1,024개지만 20개의 후보는 1,048,576개다. 알고리즘 이름만 보고 실행 가능성을 판단하지 말고, 후보 개수에 후보 하나의 검사 비용을 곱해 보아야 한다.

가지치기(pruning)는 답이 될 수 없는 중간 선택을 더 확장하지 않는 방법이다. 하지만 어떤 선택을 버려도 되는지 근거가 먼저 필요하다. 이번 기록에는 음수가 있으므로 현재 합이 목표보다 크다는 이유만으로 버릴 수 없다. 예를 들어 목표가 4일 때 5를 먼저 골라도 뒤의 -1을 함께 고르면 답이 된다. 이 장에서는 모든 선택을 검사하는 기준을 세운다. 다음 장에서는 작은 문제를 연결해 후보를 만드는 구조를 다룬다.

검증용 느린 정답은 product((0, 1), repeat=n)으로 모든 선택표를 직접 만든다. 이 방식도 지수 시간이 들지만, 선택표와 합 계산의 관계가 드러나 기준으로 읽기 쉽다. 세 풀이와 기준 풀이가 서로 다른 생성 구조를 사용하면 같은 실수를 공유할 가능성을 줄일 수 있다. 일치 검사는 정확성 설명을 대신하지 않으며, 설명에서 놓친 경계를 찾는 보조 수단이다.

완성 코드

다음을 main.py로 저장한다. 예시 데이터는 코드 안의 문자열로 두고 StringIO로 읽는다. 순열과 조합 예제도 직접 구현과 라이브러리의 결과를 비교한다. 부분집합 검증은 길이 0부터 4까지, 값이 -1·0·1인 모든 배열과 목표 -3부터 3까지를 사용한다. 난수를 사용하지 않아 매번 같은 입력을 같은 순서로 검사한다.

from io import StringIO
from itertools import combinations, permutations, product


def permutation_indices(n, r):
    paths = [()]
    for _ in range(r):
        next_paths = []
        for path in paths:
            for i in range(n):
                if i not in path:
                    next_paths.append(path + (i,))
        paths = next_paths
    return paths


def combination_indices(n, r):
    paths = [()]
    for _ in range(r):
        next_paths = []
        for path in paths:
            start = path[-1] + 1 if path else 0
            for i in range(start, n):
                next_paths.append(path + (i,))
        paths = next_paths
    return paths


def solve_direct(values, target):
    subsets = [()]
    for i in range(len(values)):
        added = [chosen + (i,) for chosen in subsets]
        subsets.extend(added)

    answers = []
    for chosen in subsets:
        if sum(values[i] for i in chosen) == target:
            answers.append(chosen)
    return sorted(answers)


def solve_combinations(values, target):
    answers = []
    n = len(values)
    for size in range(n + 1):
        for chosen in combinations(range(n), size):
            if sum(values[i] for i in chosen) == target:
                answers.append(chosen)
    return sorted(answers)


def solve_bitmask(values, target):
    answers = []
    n = len(values)
    for mask in range(1 << n):
        chosen = tuple(
            i for i in range(n) if mask & (1 << i)
        )
        if sum(values[i] for i in chosen) == target:
            answers.append(chosen)
    return sorted(answers)


def slow_reference(values, target):
    answers = []
    for flags in product((0, 1), repeat=len(values)):
        total = 0
        chosen = []
        for i, flag in enumerate(flags):
            if flag == 1:
                total += values[i]
                chosen.append(i)
        if total == target:
            answers.append(tuple(chosen))
    return sorted(answers)


def check_small_inputs():
    solvers = (
        solve_direct,
        solve_combinations,
        solve_bitmask,
    )
    cases = 0
    for n in range(5):
        for values in product((-1, 0, 1), repeat=n):
            for target in range(-3, 4):
                expected = slow_reference(values, target)
                for solve in solvers:
                    actual = solve(values, target)
                    if actual != expected:
                        raise AssertionError(
                            (solve.__name__, values,
                             target, expected, actual)
                        )
                cases += 1
    return cases


def main():
    source = StringIO("4 4\n2 -1 3 2\n")
    n, target = map(int, source.readline().split())
    values = list(map(int, source.readline().split()))
    if len(values) != n:
        raise ValueError("기록 개수가 맞지 않다")

    routes = permutation_indices(3, 2)
    displays = combination_indices(4, 2)
    if routes != list(permutations(range(3), 2)):
        raise AssertionError("방문 순서가 다르다")
    if displays != list(combinations(range(4), 2)):
        raise AssertionError("진열 묶음이 다르다")

    direct = solve_direct(values, target)
    combined = solve_combinations(values, target)
    masked = solve_bitmask(values, target)
    if not (direct == combined == masked):
        raise AssertionError("세 풀이의 결과가 다르다")

    cases = check_small_inputs()
    print(f"방문 순서 후보: {len(routes)}")
    print(f"진열 묶음 후보: {len(displays)}")
    print(f"기록: {values}, 목표: {target}")
    print(f"직접 구현: {direct}")
    print(f"조합: {combined}")
    print(f"비트마스크: {masked}")
    print("세 방법 일치: True")
    print(f"작은 입력 전수 대조: {cases}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

StringIO는 문자열을 파일처럼 읽게 한다. 첫 줄에서 기록 수와 목표를 읽고, 다음 줄에서 기록을 읽는다. readline().split()과 map(int, ...)을 사용하므로 코딩 테스트의 줄 단위 입력 처리와 같은 형태를 연습할 수 있다. 실제 표준 입력을 기다리는 input()은 사용하지 않는다.

permutation_indices의 paths = [()]는 아직 아무것도 고르지 않은 경로 하나를 뜻한다. 빈 목록 []으로 시작하면 확장할 후보가 없어 결과가 계속 비어 있게 된다. path + (i,)에서 쉼표는 원소 하나인 튜플을 만들기 위해 필요하다.

combination_indices의 start는 중복 표현을 막는 경계다. 첫 선택은 0부터 가능하고, 다음 선택은 마지막 인덱스보다 커야 한다. 반복문이 끝났을 때 각 튜플은 오름차순이므로 같은 묶음의 다른 나열이 생성되지 않는다.

solve_direct는 새 인덱스를 붙인 목록 added를 먼저 완성한다. 그다음 extend를 호출하므로 한 단계에서 같은 인덱스를 반복해서 붙이지 않는다. subsets에는 빈 튜플도 남으며, 빈 튜플을 합산한 값은 0이다.

solve_combinations의 range(n + 1)은 크기 0과 크기 n을 모두 포함한다. range(n)으로 쓰면 모든 기록을 골라야만 나오는 답을 놓친다. chosen 자체가 인덱스 튜플이므로 추가 변환 없이 정답 목록에 넣는다.

solve_bitmask의 바깥 반복문은 빈 선택에 해당하는 마스크 0도 검사한다. 안쪽 튜플 생성식은 켜진 자리의 인덱스를 작은 순서로 모은다. 괄호로 묶은 1 << i는 어떤 자리와 비교하는지 명확히 보여 준다.

세 함수가 반환하는 sorted(answers)는 튜플의 사전식 순서를 사용한다. 앞 원소부터 비교하고, 공통 부분이 같으면 짧은 튜플이 먼저 온다. 따라서 예시 결과에서 (0, 1, 2)는 (0, 3)보다 앞선다. 선택 개수가 적은 순서로 정렬한 결과는 아니다.

slow_reference는 선택 여부를 0과 1의 튜플로 받는다. 선택한 자리만 합에 더하고 인덱스를 따로 모으므로 비트 연산을 사용하지 않는다. 각 함수가 결과를 정렬하므로 목록 전체를 비교해 누락, 잘못된 추가, 중복까지 확인할 수 있다.

check_small_inputs에서는 배열이 총 1 + 3 + 9 + 27 + 81 = 121개다. 배열마다 목표 7개를 검사하므로 사례 수는 847개다. 길이 0도 포함하므로 빈 입력과 빈 선택의 처리를 확인한다. 같은 값의 반복, 음수와 양수의 상쇄, 목표를 만들 수 없는 경우도 검사 범위에 들어간다.

불일치가 있으면 함수 이름과 입력, 기대 결과, 실제 결과를 예외에 담는다. 단순히 실패했다고 출력하는 것보다 어느 조건에서 어긋났는지 바로 좁힐 수 있다. 여기서는 assert 문 대신 명시적인 예외를 사용하므로 최적화 실행 옵션에 따라 검사가 생략되지 않는다.

실행 결과

macOS 또는 Linux에서 Python 3.12 이상으로 실행한다. 첫 명령은 구문 컴파일을 확인하고, 다음 명령은 프로그램을 실행한다. 구문 컴파일이 성공하면 별도 출력 없이 끝난다.

python3 -m py_compile main.py
python3 main.py

예상 출력은 다음과 같다.

방문 순서 후보: 6
진열 묶음 후보: 6
기록: [2, -1, 3, 2], 목표: 4
직접 구현: [(0, 1, 2), (0, 3), (1, 2, 3)]
조합: [(0, 1, 2), (0, 3), (1, 2, 3)]
비트마스크: [(0, 1, 2), (0, 3), (1, 2, 3)]
세 방법 일치: True
작은 입력 전수 대조: 847개 통과

인덱스 (0, 1, 2)는 2 + (-1) + 3, (0, 3)은 2 + 2, (1, 2, 3)은 -1 + 3 + 2를 뜻한다. 세 합은 모두 4다. 같은 값 2가 서로 다른 위치에 있으므로 첫째와 셋째 결과는 별개의 기록 묶음이다.

실무에서 자주 틀리는 것

값을 집합으로 바꾸어 기록을 잃는다

값의 중복과 선택의 중복은 다르다. 다음 코드는 입력의 같은 값을 합쳐 버려 두 기록을 함께 선택할 가능성을 없앤다.

# 틀린 코드
values = list(set([2, -1, 3, 2]))

기록의 위치가 의미를 갖는 문제라면 원래 목록을 유지하고 인덱스로 선택한다.

# 고친 코드
values = [2, -1, 3, 2]
for chosen in combinations(range(len(values)), 2):
    total = sum(values[i] for i in chosen)

비트마스크에서 0을 건너뛴다

다음 반복문은 빈 부분집합을 검사하지 않는다. 목표가 0이면 빈 선택도 답으로 인정하는 이 문제의 조건과 어긋난다.

# 틀린 코드
for mask in range(1, 1 << n):
    pass

0부터 시작하면 된다. 문제에서 적어도 하나를 고르라고 명시했다면 그때 빈 선택을 제외한다.

# 고친 코드
for mask in range(1 << n):
    pass

순회 중인 목록에 새 후보를 계속 붙인다

다음 코드는 새로 붙인 후보도 같은 반복문의 순회 대상이 된다. 후보가 계속 늘고 같은 인덱스가 반복해서 붙는다.

# 틀린 코드
for chosen in subsets:
    subsets.append(chosen + (i,))

현재 단계의 후보와 다음에 추가할 후보를 분리한다. 이렇게 해야 인덱스 하나를 한 단계에서 한 번만 처리한다는 불변식을 유지한다.

# 고친 코드
added = [chosen + (i,) for chosen in subsets]
subsets.extend(added)

부분합이 크다는 이유로 후보를 버린다

음수가 있으면 나중에 합이 작아질 수 있다. 다음 코드는 [5, -1]에서 두 기록을 골라 목표 4를 만드는 경우를 놓친다.

# 틀린 코드
total = 0
for i in chosen:
    total += values[i]
    if total > target:
        break
else:
    if total == target:
        answers.append(chosen)

이 장의 조건에서는 끝까지 합산한 뒤 판정한다. 일부 후보를 생략하려면 남은 기록으로도 목표를 만들 수 없다는 별도의 근거가 필요하다.

# 고친 코드
total = sum(values[i] for i in chosen)
if total == target:
    answers.append(chosen)

한눈에 보기

후보를 만드는 규칙과 검사해야 할 경계를 함께 정리한다

선택 구조	직접 만드는 규칙	표준 라이브러리	확인할 경계
순열	사용하지 않은 인덱스를 붙인다	permutations	순서가 다르면 다른 후보인가
조합	마지막보다 큰 인덱스를 붙인다	combinations	같은 묶음의 순서 중복을 막았는가
부분집합	기존 후보와 새 원소를 붙인 후보를 합친다	모든 크기의 combinations	빈 선택과 전체 선택이 있는가
비트마스크	0부터 2ⁿ-1까지 검사한다	비트 연산으로 구현한다	오른쪽 끝이 인덱스 0인가

완전 탐색의 설명은 세 질문으로 정리할 수 있다. 유효한 후보가 모두 만들어지는가, 같은 후보를 잘못 중복시키지 않는가, 후보 하나의 판정이 문제 조건과 일치하는가다. 이 세 가지를 확인한 뒤 후보 수와 검사 비용을 계산하면 구현과 실행 가능성을 함께 판단할 수 있다.

연습 문제

1. 방문 후보가 네 곳이고 서로 다른 세 곳을 순서 있게 방문한다. 후보 수를 구하고, permutation_indices와 permutations의 결과가 같은지 검사하라. 이어서 순서를 무시하고 세 곳만 고를 때의 후보 수도 구하라.
2. 재고 기록이 [0, 0, 2], 목표가 0일 때 정답 인덱스 튜플을 모두 적어라. 빈 부분집합을 금지하면 어떤 결과만 제외되는지 설명하라.
3. 네 기록에서 마스크 10이 선택하는 인덱스를 구하라. 선택 여부를 표시한 네 자리 이진수와, 완성 코드의 예시 기록에서 해당 선택의 합을 적어라.
4. 완성 코드의 전수 대조에서 최대 길이를 5까지 포함하도록 바꾸려 한다. 바꿀 반복문과 전체 사례 수를 구하라. 검사 범위에 [5, -1]과 목표 4도 별도로 넣는 이유를 설명하라.

정답과 해설

1. 순서를 구분하면 4 × 3 × 2 = 24개다. 첫 방문지는 네 곳, 둘째는 남은 세 곳, 셋째는 남은 두 곳이다. 순서를 무시하면 네 곳 중 제외할 한 곳을 정하는 것과 같으므로 4개다. 아래 코드는 생성 결과 전체를 비교한다.

   assert permutation_indices(4, 3) == list(
       permutations(range(4), 3)
   )
   assert combination_indices(4, 3) == list(
       combinations(range(4), 3)
   )

2. 정렬된 결과는 [(), (0,), (0, 1), (1,)]다. 값 2인 기록은 다른 음수가 없어 포함할 수 없다. 두 0은 서로 다른 기록이므로 각각 고르거나 함께 고르는 경우가 모두 존재한다. 빈 부분집합을 금지하면 ()만 제외한다. 목표가 0이라는 이유로 다른 결과까지 제외해서는 안 된다.

3. 마스크 10은 이진수 1010이다. 오른쪽 끝부터 인덱스를 붙이면 켜진 자리는 1과 3이므로 선택은 (1, 3)이다. 예시 기록에서 합은 -1 + 2 = 1이다. 마스크의 숫자 10은 합이나 선택 개수를 뜻하지 않으며, 선택 여부를 담은 표현이다.

4. for n in range(6):으로 바꾼다. 배열 수는 1 + 3 + 9 + 27 + 81 + 243 = 364개이고 목표가 일곱 가지이므로 사례 수는 364 × 7 = 2548개다. 값의 범위를 -1·0·1로 제한한 전수 검사에는 [5, -1]이 없다. 따라서 부분합이 목표를 넘었다가 음수로 다시 내려오는 특정 실수를 직접 드러내는 회귀 사례로 추가할 수 있다.

   for solve in (
       solve_direct, solve_combinations, solve_bitmask
   ):
       assert solve([5, -1], 4) == [(0, 1)]