부분집합 합(SubSet Sum) 문제 – 백트래킹 알고리즘으로 해결하기

부분집합 합 문제는 정수 원소들로 이루어진 하나의 집합과 목표 합계 값이 주어졌을 때, 집합의 부분집합 중에서 그 합이 목표 값과 일치하는 모든 부분집합을 찾는 문제입니다.

이 문제는 백트래킹(Backtracking) 기법으로 효율적으로 해결할 수 있습니다. 백트래킹은 가능한 해를 하나씩 시도해 보다가, 현재 선택한 원소가 유효하지 않으면 이전 상태로 되돌아가(백트랙) 다른 원소를 추가하는 방식으로 탐색을 진행합니다. 이렇게 하면 불필요한 경우의 수를 가지치기(pruning)하며 전체 탐색 공간을 크게 줄일 수 있습니다.

입력과 출력

입력:
정수들의 집합과 목표 합계 값을 입력으로 받습니다.
집합(Set): {10, 7, 5, 18, 12, 20, 15}
목표 합계(Sum): 35

출력:
각 부분집합의 원소 합이 목표 합계와 같은 모든 부분집합을 출력합니다.
{10, 7, 18}
{10, 5, 20}
{5, 18, 12}
{20, 15}

알고리즘

subsetSum(set, subset, n, subSize, total, node, sum)

입력 − 주어진 집합과 부분집합 배열, 집합의 크기(n), 현재 부분집합의 크기(subSize), 부분집합 원소들의 합(total), 탐색 시작 노드(node), 목표 합계(sum).

출력 − 합이 목표 값과 같은 모든 가능한 부분집합.

Begin
    if total = sum, then
        부분집합을 출력한다
        // 다음 부분집합을 찾기 위해 계속 진행
        subsetSum(set, subset, n, subSize-1, total-set[node], node+1, sum)
        return
    else
        for 집합의 각 원소 i에 대해, do
            subset[subSize] := set[i]
            subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
        done
End

동작 원리

알고리즘은 재귀적으로 동작합니다. 현재까지 선택한 원소들의 합(total)이 목표 합(sum)과 같으면 해당 부분집합을 출력하고, 마지막에 추가된 원소를 제거한 뒤 다음 노드부터 다시 탐색을 이어갑니다. 아직 목표에 도달하지 못했다면, 현재 노드 이후의 원소들을 차례로 부분집합에 추가하며 깊이 우선으로 탐색을 반복합니다. 이미 확인한 원소를 다시 선택하지 않도록 시작 인덱스를 관리함으로써 중복되는 부분집합의 생성을 방지합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

void displaySubset(int subSet[], int size) {
    for(int i = 0; i < size; i++) {
        cout << subSet[i] << "  ";
    }
    cout << endl;
}

void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
    if( total == sum) {
        displaySubset(subSet, subSize);     // 부분집합 출력
        subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     // 다른 부분집합 탐색
        return;
    }else {
        for( int i = nodeCount; i < n; i++ ) {     // 너비 방향으로 노드 탐색
            subSet[subSize] = set[i];
            subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);     // 깊이 방향의 다음 노드 처리
        }
    }
}

void findSubset(int set[], int size, int sum) {
    int *subSet = new int[size];     // subsetSum 함수에 전달할 부분집합 배열 생성
    subsetSum(set, subSet, size, 0, 0, 0, sum);
    delete[] subSet;
}

int main() {
    int weights[] = {10, 7, 5, 18, 12, 20, 15};
    int size = 7;
    findSubset(weights, size, 35);
}

실행 결과