[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를 포함한 전체 소스코드는 다음과 같다.

	#include <stdio.h>
	#include <stdlib.h>
	#include <vector>
	#include <map>
	#include <cassert>
	#include <cstring>
	using namespace std;
	// problem statement
	// implement a function which receive vector<int> v
	// and return true if some elements of v can sum up to zero
	// ex) v: {3, 7, 2, -5} ==> {3, 2, -5} can be sum up to zero ==> return true
	//#define NOT_IMPLMENTED(exp) do {if(!exp) assert(false);} while(0)
	//end not-inclusive
	//[start, end)
	//if b_allow_duplicate is false, elements will not duplicated
	vector<int> get_random_array(int start, int end, int count, bool b_allow_duplicate = true, bool b_avoid_zero = true)
	{
	assert(b_allow_duplicate == true); // false, not implemented
	int offset = 0;
	if(start <0) offset=start;
	start += offset;
	end += offset;
	vector<int> r;
	for(int i=0;i<count;i++)
	{
	int n1 = rand() % (end - start) + start - offset;
	if(b_avoid_zero && n1==0) n1=1;
	r.push_back(n1);
	}
	return r;
	}
	void print(vector<int>& v)
	{
	printf("input: ");
	for(int i=0;i<(int)v.size();i++) printf("%d ", v[i]);
	printf("\n");
	}
	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);
	}
	bool naive(vector<int>& v)
	{
	int n = (int)v.size();
	assert(n < 10);
	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;
	}
	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;
	}
	int main()
	{
	for(int i=0;i<100000;i++)
	{
	vector<int> v = get_random_array(-20, 20, 6);
	print(v);
	bool r1 = naive(v);
	bool r2 = recursive(v);
	bool r3 = dp(v);
	assert(r1 == r2 && r2 == r3);
	printf("result: %s\n", r1?"possible":"impossible");
	}
	return 0;
	}

view raw subset_sum.cpp hosted with ❤ by GitHub