Partition Equal Subset Sum.

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution :

We can solve this problem by using tabulation approach (Dynamic programming). This problem is variation of Knapsack 0–1. In Knapsack , we have been given some set of values and target weight/sum. We will have to make that sum by using those value. We will have two case for each given values.

1. select the value to make that sum.
2. Do not select and move to next value.

First we have to create a two dimension table where we we will populate the DP table based on the result if we select each individual values .

Please find the code in C#.

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];
}
}
}