#include "stdafx.h"

bool isSubsetSum(int set[], int n, int sum)
{
	bool sumOfSubSet[100][100];

	for (int i=0; i<100; i++)
	{
		for (int j=0; j<100; j++)
		{
			sumOfSubSet[i][j] = false;
		}
	}

	/*
	*   F[i][j]  ±ì ? ￥”1-i÷–—°?°μ? ?÷–￡¨∫??? j μ? ?∑ò￥ê‘?
	*   true ±ì ?￥ê‘? false ±ì ?≤a￥ê‘?
	*/


	for (int j=0; j<=sum; j++)
		sumOfSubSet[0][j] = false;

	for (int i=0; i<=n; i++)
		sumOfSubSet[i][0] = false;

	sumOfSubSet[0][0] = true;



	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=sum; j++)
		{
			sumOfSubSet[i][j] = sumOfSubSet[i-1][j];

			if ((j-set[i-1] >= 0) && (sumOfSubSet[i][j-set[i-1]]))
			{
				sumOfSubSet[i][j] = true;
			}
		}
	}

	return sumOfSubSet[n][sum];
}



int _tmain(int argc, _TCHAR* argv[])
{
	int set[] = {3, 34, 4, 12, 5, 2};
	int sum = 13;
	int n = sizeof(set)/sizeof(set[0]);
	if (isSubsetSum(set, n, sum) == true)
		 printf("Found a subset with given sum");
	else
		 printf("No subset with given sum");
	return 0;
}