# Subset Sum Problem – Dynamic Programming

Given a set of positive integers and a value sum write program to determine if there is a subset of the given set with sum equal to given sum.

For e.g.

``````sum=34
arr = {4, 8, 12, 18}``````

subset {4,12,18} has the sum 34

#### Solution Using Dynamic Programming Approach

We will find whether if there is exists any subset of with provided sum 1 if it’s existed store it in array and then start finding for sum 2 and so on.

Time complexity of this solution is O(n*Sum).

``````using System;
namespace SubSetSum{
class Program
{
static void Main()
{
var arr = new[] { 4, 8, 12, 18 };
var sum = 34;
var result = SubSet(arr, arr.Length, sum);
Console.WriteLine(result? "Found a subset with given sum" : "No subset with given sum");
}

static bool SubSet(int[] a, int n, int sum)
{
var dp = new bool[n + 1, sum + 1];
for (var i = 0; i <= n; i++)
dp[i, 0] = true;
for (var j = 1; j <= sum; j++)
dp[0, j] = false;
for (var i = 1; i <= n; i++)
{
for (var j = 1; j <= sum; j++)
{
if (dp[i - 1, j])
{
dp[i, j] = true;
}
else
{
if (a[i - 1] > j)
dp[i, j] = false;
else
dp[i, j] = dp[i - 1, j - a[i - 1]];
}
}
}
return dp[n, sum];
}
}

} ``````