Partition Equal Subset Sum.

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  1. select the value to make that sum.
  2. Do not select and move to next value.
using System;namespace DotNetProject
{
public class DPClass
{
public static bool CanPartition(int[] num){ int n = num.Length; int sum = 0; for (int i = 0; i < n; i++)
{
sum += num[i];
}
int target = sum/2; bool[,] dp = new bool[n + 1, target + 1]; for (int i = 0; i < dp.GetLength(0); i++)
{
for (int j = 0; j < dp.GetLength(1); j++)
{
if (i == 0 && j == 0)
dp[i, j] = true;
else if (i == 0)
dp[i, j] = false;
else if (j == 0)
dp[i, j] = true;
else
{
if(dp[i-1,j])
dp[i,j] = true;
else
{
int val = num[i-1];
if(j >= val)
{
if(dp[i-1, j - val])
dp[i,j] = true;
}
}
}
}
}
return dp[n,target];}
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store