[C/C++] 프로젝트 오일러 #103 Special Subset Sums: Optimum(백트래킹)

Project Euler #103: Special Subset Sums: Optimum

이 문제는 “특수 부분집합”의 성질과 최적의 집합을 찾는 문제입니다.

문제 설명

1. 집합 S에 대해, S의 모든 부분집합이 서로 다른 합을 가져야 합니다.
• 즉, S의 두 부분집합 A, B에 대해 \(  \text{sum}(A) \neq \text{sum}(B) \) 여야 합니다.
• 여기서 집합 A와 B는 같은 원소가 존재하지 말아야 합니다 (\( A \cap B = \emptyset \)).
2. S의 부분집합이 특정 조건을 만족해야 합니다:
• \(  |A| > |B|  \) 이면 \(  \text{sum}(A) > \text{sum}(B) \) 여야 합니다. (\( |A| \) 는 부분집합 A의 원소 개수)
3. S의 크기가 주어질 때, 최적의 집합 S를 찾는 것이 목표입니다.
• 최적의 집합은 S 원소의 합이 최소가 되는 집합입니다.

n = 4일 때, 
집합 \(  S = \{a, b, c, d\} \)  (\( a < b < c < d \))를 고려합니다. 다음 조건을 만족해야 합니다:
1. 모든 부분집합의 합이 서로 달라야 합니다.
2. 큰 크기의 부분집합은 작은 크기의 부분집합보다 합이 더 커야 합니다.

가능한 집합 탐색:
• \(  S = \{3, 5, 6, 7\} \) 이라고 가정해 봅시다.
• 모든 부분집합을 구합니다:
• \( \{3\}, \{5\}, \{6\}, \{7\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\}, \{3, 5, 6\}, \{3, 5, 7\}, \dots \)
• 각 부분집합의 합을 구해보면:
\( \{3\} = 3, \{5\} = 5, \{6\} = 6, \{7\} = 7, \{3, 5\} = 8, \dots \)

모든 부분집합의 합이 서로 다른지 확인합니다.

• 이 경우, 조건을 만족하며 원소 합이 \(  3 + 5 + 6 + 7 = 21 \) 입니다.
• 하지만 더 작은 합을 가지는 다른 S를 찾을 수도 있습니다.

set

 

제가 문제를 풀기 위한 소스는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #103 - Special Subset Sums: Optimum
//        - by Aubrey Choi
//        - created at 2015-04-15
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define    TARGET    7
#define    TSUM    (1<<TARGET)

//    Total sum must be larger and equal to 2^n-1.

bool Check(int sss[], int n)
{
    int cb[4096];
    int suma = sss[0], sumb = 0;
    for( int r = 1 ; r <= n/2 ; r++ )
    {
        suma += sss[r];
        sumb += sss[n-r];
        if( suma <= sumb ) return false;
    }

    cb[0] = 0;
    for( int i = 0 ; i < n ; i++ )
    {
        for( int j = 0 ; j < (1<<i) ; j++ )
        {
            int c = cb[(1<<i)+j] = cb[j]+sss[i];
            for( int k = 1 ; k < (1<<i) ; k++ )
                if( c == cb[k] ) return false;
        }
    }

    return true;
}

bool rec(int sss[], int n, int k, int s, int sum)
{
    if( sum < 0 ) return false;
    if( k == n ) return Check(sss, k);
    if( k > 2 && Check(sss, k) == false ) return false;
    while( s*(n-k)+(n-k)*(n-k-1)/2 < sum )
    {
        sss[k] = s;
        if( rec(sss, n, k+1, s+1, sum-s) ) return true;
        s++;
    }
    return false;
}

int main()
{
    int sss[TARGET];

    for( int i = TSUM-1 ; ; i++ ) if( rec(sss, TARGET, 0, 1, i) ) break;
    printf("ans = ");
    for( int i = 0 ; i < TARGET ; i++ ) printf("%d", sss[i]);
    putchar('\n');
}

#if 0
//    { a1, a2, ..., an } is special sum at number of set is n.
//    m = [n/2]+1
//    next set's first elemenet is am.

bool rec(int m[], int n, int k)
{
    if( k == 0 )
    {
        m[0] = 0;
        int ans[TARGET];
        int s[TSUM];
        memcpy(s, m, sizeof(s));
        for( int i = 0 ; i < TARGET ; i++ )
        {
            ans[i] = s[1]; s[1] = 0;
            for( int j = 1 ; j < (TSUM>>(i+1)) ; j++ )
            {
                int t = 0;
                int k;
                for( k = j+1 ; k < (TSUM>>i) ; k++ )
                    if( s[k] ) { t = s[k]; s[k] = 0; break; }
                for( k++ ; k < (TSUM>>i) ; k++ )
                    if( s[k] == t+ans[i] ) { s[k] = 0; break; }
                if( k >= (TSUM>>i) ) return false;
                s[j] = t;
            }
        }

        //    2nd rule test.
        int suma = ans[0], sumb = 0;
        for( int r  = 1 ; r <= (TARGET-1)/2; r++ )
        {
            suma += ans[r]; sumb += ans[TARGET-r];
            if( suma <= sumb ) return false;
        }

        //    print answer.
        for( int i = 0 ; i < TARGET ; i++ ) printf("%d", ans[i]); printf("\n");

        return true;
    }
    for( int i = k ; i < m[k+1] ; i++ )
    {
        m[k] = i;
        if( rec(m, n, k-1) ) return true;
    }
    return false;
}

int main()
{
    int m[TSUM];
    int n = TSUM;

    for( int i = n-1 ; ; i++ )
    {
        m[n-1] = i;
        if( rec(m, n, n-2) ) break;
    }

    return 0;
}
#endif

 

문제 해결을 위한 알고리즘 기법

위 코드는 Project Euler #103의 문제를 해결하기 위해 다음과 같은 기법을 사용합니다:
1. 부분집합 검증 (Check 함수):
• S의 모든 부분집합이 서로 다른 합을 가지는지 확인합니다.
• 추가적으로 “큰 크기의 부분집합은 더 큰 합을 가져야 한다”는 규칙도 검증합니다.
2. 재귀 탐색 (rec 함수):
• S의 가능한 조합을 재귀적으로 탐색합니다.
• 부분집합 합이 최소가 되는 최적 집합을 찾습니다.
• 재귀 중간 단계에서 조건이 불만족하면 조기에 탐색을 종료(백트래킹)하여 효율성을 높입니다.
3. 최적화된 범위 설정:
• S 의 최소 값에서 시작하여 S의 가능한 값들을 생성하고, 각 단계에서 전체 합 sum과 비교하여 탐색 범위를 제한합니다.

코드 분석: 중요한 부분 설명

1. 부분집합 검증: Check 함수

bool Check(int sss[], int n) {
    int cb[4096];
    int suma = sss[0], sumb = 0;
    for (int r = 1; r <= n/2; r++) {
        suma += sss[r];
        sumb += sss[n-r];
        if (suma <= sumb) return false; // 조건 2 위반
    }

    cb[0] = 0; // 부분집합 합 저장 배열
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << i); j++) {
            int c = cb[(1 << i) + j] = cb[j] + sss[i];
            for (int k = 1; k < (1 << i); k++)
                if (c == cb[k]) return false; // 조건 1 위반
        }
    }

    return true; // 모든 조건을 만족
}

주요 동작:
• 조건 2: 큰 부분집합의 합이 항상 작은 부분집합의 합보다 크도록 확인.
• 조건 1: cb 배열에 각 부분집합의 합을 저장하여 중복 확인.

2. 재귀 탐색: rec 함수

bool rec(int sss[], int n, int k, int s, int sum) {
    if (sum < 0) return false; // 합 초과
    if (k == n) return Check(sss, k); // 부분집합 검증
    if (k > 2 && Check(sss, k) == false) return false; // 중간 검증

    while (s * (n - k) + (n - k) * (n - k - 1) / 2 < sum) {
        sss[k] = s;
        if (rec(sss, n, k + 1, s + 1, sum - s)) return true; // 다음 값 탐색
        s++;
    }

    return false; // 탐색 실패
}

주요 동작:
• s부터 시작하여 n개의 집합을 재귀적으로 탐색합니다.
• s*(n-k) 로 남은 값의 최소 합을 예측하여 조기 종료.

3. 메인 함수: 탐색 시작

int main() {
    int sss[TARGET];

    for (int i = TSUM - 1; ; i++) {
        if (rec(sss, TARGET, 0, 1, i)) break; // 최적 집합 탐색
    }

    printf("ans = ");
    for (int i = 0; i < TARGET; i++) printf("%d", sss[i]);
    putchar('\n');
}

주요 동작:
• 가능한 총합 sum을 최적화된 S를 찾을 때까지 증가시키며 탐색.