[algorithm] subset sum

다음의 문제를 생각해보자.

배열이 하나 주어진다.

{3, -2, 5, 7, -3, 1}

이 때 이 배열의 일부 원소를 더해서 0이 되는 경우가 있는지 알아내는 프로그램을 작성한다고 해보자.

위 배열에 대한 답은 True이다 {-2, 5, -3}을 부분집합으로 취해 더하면 0을 만드는 것이 가능하기 때문이다.

subset sum 문제는 NP-complete 문제중 가장 단순한 형태로서, brute-force 이외에 P솔루션이 존재하지 않는다.

brute-force의 시간 복잡도는 모든 부분집합을 구해서 더해보는 것이기 때문에 $O(2^n)$이 된다.

다만, dynamic-programming을 쓸 경우, 반복계산을 cache하는 방법으로 수행속도를 빠르게 할 수 있으나 바로 그 cache한다는 속성 때문에 n의 범위가 커지면 메모리 초과로 쓸 수 없다.

오늘은 subset sum문제를 푸는 세 가지 방법을 검토해보자.

첫번째 방법은 재귀를 이용해서 푸는 방법이다.

bool go(vector<int>&v, int ix, int cur_sum, int count)
{
    if(ix==(int)v.size())
    {
        if(cur_sum==0&&count>0) return true;
        return false;
    }
    bool r1 = go(v, ix+1, cur_sum+v[ix], count+1);
    bool r2 = go(v, ix+1, cur_sum, count);
    return r1 || r2;
}

bool recursive(vector<int>& v)
{
    return go(v, 0, 0, 0);
}

두번째 방법은 binary operation을 사용해 재귀없이 loop 로 푸는 방법이다.

bool naive(vector<int>& v)
{
    int n = (int)v.size();
    for(int i=1;i<(1<<n);i++)
    {
        int s = 0;
        for(int j=0;j<n;j++) if((1<<j)&i) s+=v[j];
        if(s==0) return true;
    }
    return false;
}

위 두 가지방법은 시간 복잡도가 $O(2^n)$이기 때문에 n이 20만 넘어도 너무 느려져서 쓸 수 없게 된다.

다음 세번째 방법은 dynamic programming(이하 dp)을 사용해서 푸는 방법이다.

bool dp(vector<int>& v)
{
    map<int, bool> m, m2;
    for(int i=0;i<(int)v.size();i++)
    {
        m2 = m;
        for(auto it=m.begin();it!=m.end();it++)
        {
            m2[it->first + v[i]] = true;
        }
        m2[v[i]] = true;
        m = m2;
    }
    if (m[0]) return true;
    return false;

}

위의 세번째 방법은 n의 범위가 너무 크지 않은 경우 상당히 빠른시간을 보장한다($O(n \times m)$)

m은 n의 범위(최대값)이 되겠다. 최대값이 작은 경우는 다항시간에 가까운 실행시간을 보장한다.

testcase를 포함한 전체 소스코드는 다음과 같다.