Skip to content

Instantly share code, notes, and snippets.

@riyadparvez
Created July 20, 2013 18:24
Show Gist options
  • Save riyadparvez/6045979 to your computer and use it in GitHub Desktop.
Save riyadparvez/6045979 to your computer and use it in GitHub Desktop.
Implementation of subset sum problem using dynamic programming approach in C#.
public static bool SubsetSum(IEnumerable<int> list, int s)
{
var arr = list.ToArray();
Array.Sort(arr);
var a = arr.Where(i => i < 0).Sum();
var b = arr.Where(i => i > 0).Sum();
if(a > s || b < s)
{
return false;
}
var dp = new bool[arr.Length+1, s+1];
for (int i = 0; i <= s; i++)
{
dp[0, i] = false;
}
for (int j = 1; j <= s; j++)
{
for (int i = 1; i <= arr.Length; i++)
{
dp[i, j] = (arr[i - 1] == j) || dp[i - 1, j] ||
((j - arr[i - 1] >= arr.Take(i).Where(number => number < 0).Sum())
&& (j - arr[i - 1] <= arr.Take(i).Where(number => number > 0).Sum())
&& dp[i - 1, j - arr[i - 1]]);
}
}
return dp[arr.Length, s];
}
@ZackStone
Copy link

best solution

@pvmraghunandan
Copy link

any better solution for handling float values?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment