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");
            Console.ReadLine();
        }
        
            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];
            }
    }
    
} 

Leave a Reply

Your email address will not be published. Required fields are marked *