Algorithms/subset_sum.cpp at master · macanhhieu/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>

using namespace std;

bool subset_sum(int set[],int n,int sum)
{
	bool dp[n+1][sum+1];
	for(int i=0;i<=n;++i)
	{

		for(int j=0;j<=sum;++j)
		{
			if(i==0)
		    {
			    dp[0][j] = false;
		    }
			if(j==0)
			{
				dp[i][0]= true;
			}
			if(j<set[i-1])
			{
				dp[i][j]=dp[i-1][j];
			}
			if(j>=set[i-1])
			{
				dp[i][j]=dp[i-1][j]||dp[i-1][j-set[i-1]];
			}
		}
	}
	return dp[n][sum];
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin>>n;
   int set[n];
   for(int i=0;i<n;++i)
   {
   	    cin>>set[i];
   }
   int sum;
   cin>>sum;
   if(subset_sum(set,n,sum)==true)
   {
   	    cout<<"Found a subset with given sum";
   }
   else
   {
   	cout<<"No subset with given sum";
   }
   return 0;
}