부분집합의 합 문제(Subset Sum Problem)

부분집합의 합 문제(Subset Sum Problem)

• 부분집합의 합 문제를 한 문장으로 표현하면 다음과 같음.
  • 음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?

부분집합의 합 문제의 예

S = { 13, 79, 45, 29 }
x = 42 → True (13 + 29)
x = 25 → False

• 집합 S가 S = { 13, 79, 45, 29 } 형태로 주어질 경우, S로부터 다음과 같은 16개의 부분집합을 추출할 수 있음.

{ }
{ 13 }
{ 79 }
{ 45 }
{ 29 }
{ 13, 79 }
{ 13, 45 }
{ 13, 29 }
{ 79, 45 }
{ 79, 29 }
{ 45, 29 }
{ 13, 79, 45 }
{ 13, 79, 29 }
{ 13, 45, 29 }
{ 79, 45, 29 }
{ 13, 79, 45, 29 }

• 집합 S의 원소 개수와 집합 S로부터 조합 가능한 부분집합의 개수를 함께 나열하면 다음과 같음.
  • 콜론(:) 왼쪽 : 집합 S의 원소 개수
  • 콜론(:) 오른쪽 : 집합 S의 부분집합 개수

0: 1
1: 2
2: 4
3: 8
4: 16
5: 32
6: 64
7: 128
...

• 위에 나열된 숫자를 살펴보면, 원소 개수가 n인 집합 S의 전체 부분집합의 개수는 2ⁿ개임을 알 수 있음.
  • n이 증가함에 따라 부분집합의 개수가 기하급수적으로 증가함.
  • n이 10 이하의 숫자인 경우
    • 모든 부분집합을 다 검사하는 방법도 그리 나쁘지 않음.
  • 그러나 100일 경우
    • 전체 1,267,650,600,228,229,401,496,703,205,376가지의 부분집합을 검사해야 함.

 

코드

• 다음과 같이 동적 계획법(Dynamic Programming) 의 총 4가지 방법을 사용하여 코드를 작성하였음.
  • 전수 조사(Brute Force)
  • 백트래킹(Back Tracking)
  • 메모이제이션(Memoization)
  • 타뷸레이션(Tabulation)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <time.h>
#include <iomanip>
using namespace std;

#define DEBUG 0
#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

vector<string> types = {
    "BRUTE FORCE",
    "BACKTRACKING",
    "MEMOIZATION",
    "TABULATION"
};

const int UNKNOWN = INT_MAX;

void GetTime(clock_t& timer, string type) {
    // 현재 시간에서 timer를 빼서 경과 시간을 계산
    timer = clock() - timer;

    // 화면에 경과 시간 출력
    cout << type << " 방법 경과 시간: ";
    cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

    timer = clock();     // timer를 현재 시간으로 초기화
}

void GetAllSubsets(vector<int> set, vector<int> subset, int index, vector<vector<vector<int>>>& allSubsets) {
    // 집합 set의 끝에 다다른 경우
    if (index == set.size()) {
        // 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
        allSubsets[subset.size()].push_back(subset);
        return;
    }

    // 원소를 추가하지 않고 재귀 호출
    GetAllSubsets(set, subset, index + 1, allSubsets);

    // 원소를 부분집합에 추가한 후 재귀 호출
    subset.push_back(set[index]);
    GetAllSubsets(set, subset, index + 1, allSubsets);
}

bool SubsetSum_BruteForce(vector<int> set, int target) {
    vector<vector<vector<int>>> allSubsets(set.size() + 1);

    GetAllSubsets(set, {}, 0, allSubsets);

    for (int size = 0; size <= set.size(); size++) {
        PRINT("부분집합의 원소 개수: " << size << endl);

        for (auto subset : allSubsets[size]) {
            PRINT("\t{ ");

            int sum = 0;
            for (auto number : subset) {
                sum += number;
                PRINT(number << " ");
            }

            PRINT("} = " << sum << endl);

            if (sum == target) {
                return true;
            }
        }
    }
    return false;
}

bool SubsetSum_Backtracking(vector<int> &set, int sum, int i) {
    // 만약 현재 부분집합의 합이 target과 같다면
    if (sum == 0) {
        return true;
    }

    // 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
    if (i == set.size() || set[i] > sum) {
        return false;
    }

    // Case 1: sum에서 set[i]을 빼서 재귀 호출(i번째 원소를 부분집합에 추가)
    // Case 2: sum을 그대로 전달하여 재귀 호출(i번째 원소를 부분집합에 추가하지 않음.)
    return SubsetSum_Backtracking(set, sum - set[i], i + 1) || SubsetSum_Backtracking(set, sum, i + 1);
}

bool SubsetSum_Memoization(vector<int>& set, int sum, int i, vector<vector<int>>& memo) {
    // 만약 현재 부분집합의 합이 target과 같다면
    if (sum == 0) {
        return true;
    }

    // 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
    if (i == set.size() || set[i] > sum) {
        return false;
    }

    // 현재 상태가 캐시에 있는지 확인
    if (memo[i][sum] == UNKNOWN) {
        // 현재 상태에 대한 솔루션을 구하여 캐시에 저장
        bool append = SubsetSum_Memoization(set, sum - set[i], i + 1, memo);
        bool ignore = SubsetSum_Memoization(set, sum, i + 1, memo);

        memo[i][sum] = append | ignore;
    }

    // 캐시에 저장된 값을 반환
    return memo[i][sum];
}

vector<vector<bool>> SubsetSum_Tabulation(vector<int>& set) {
    int maxSum = 0;

    for (int i = 0; i < set.size(); i++) {
        maxSum += set[i];
    }

    vector<vector<bool>> DP(set.size() + 1, vector<bool>(maxSum + 1, 0));

    for (int i = 0; i < set.size(); i++) {
        DP[i][0] = true;
    }

    for (int i = 1; i <= set.size(); i++) {
        for (int sum = 1; sum <= maxSum; sum++) {
            if (sum < set[i - 1]) {
                DP[i][sum] = DP[i - 1][sum];
            }
            else {
                DP[i][sum] = DP[i - 1][sum] || DP[i - 1][sum - set[i - 1]];
            }
        }
    }

    return DP;
}

int main()  {
    vector<int> set = { 16, 1058, 22, 13, 46, 55, 3, 92, 47, 7, 98, 367, 807, 106, 333, 85, 577, 9, 3059 };
    int target = 6076;
    int tests = 4;

    sort(set.begin(), set.end());

    for (int i = 0; i < tests; i++) {
        bool found;

        clock_t timer = clock();

        switch (i) {
        case 0:
            found = SubsetSum_BruteForce(set, target);
            break;
        case 1:
            found = SubsetSum_Backtracking(set, target, 0);
            break;
        case 2: {
            // 메모이제이션 테이블 초기화
            vector<vector<int>> memo(set.size(), vector<int>(7000, UNKNOWN));
            found = SubsetSum_Memoization(set, target, 0, memo);
            break;
        }

        case 3: {
            vector<vector<bool>> DP = SubsetSum_Tabulation(set);
            found = DP[set.size()][target];
            break;
        }
        /* 가능한 부분집합 전부 출력
        case 3: {
            int total = 0;
            for (auto number : set) {
                total += number;
            }

            vector<vector<bool>> DP = SubsetSum_Tabulation(set);
            found = DP[set.size()][target];

            vector<int> subsetSums;
            for (int sum = 1; sum <= total; sum++) {
                if (DP[set.size()][sum]) {
                    subsetSums.push_back(sum);
                }
            }

            cout << "다음과 같이 " << subsetSums.size() << "가지의 부분집합의 합이 가능합니다: " << endl;

            for (auto sum : subsetSums) {
                cout << sum << " ";
            }
            cout << endl;

            break;
        }
        */
        }

        if (found) {
            cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
        }
        else {
            cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
        }

        GetTime(timer, types[i]);
        cout << endl;
    }

    return 0;
}

 

결과

원소 합이 6076인 부분집합이 있습니다.
BRUTE FORCE 방법 경과 시간: 1.36600

원소 합이 6076인 부분집합이 있습니다.
BACKTRACKING 방법 경과 시간: 0.00200

원소 합이 6076인 부분집합이 있습니다.
MEMOIZATION 방법 경과 시간: 0.00500

원소 합이 6076인 부분집합이 있습니다.
TABULATION 방법 경과 시간: 0.02000