Leetcode discuss: 416. Partition Equal Subset Sum

 Here is the link. 

Mock interview - C# - Hard to tell - add number more than once - Failed 114/115

Dec. 29, 2020
Introduction
I wrote the solution in Leetcode premium mock interview onsite from Facebook, I could not pass the test case 114/115. But I could not tell what it is wrong.

Failed test case
var test = new int[] { 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 16, 16, 16, 20, 20, 20, 20, 20, 20, 20, 20, 24, 24, 24, 24, 24, 24, 24, 24, 28, 28, 28, 28, 28, 28, 28, 28, 32, 32, 32, 32, 32, 32, 32, 32, 36, 36, 36, 36, 36, 36, 36, 36, 40, 40, 40, 40, 40, 40, 40, 40, 44, 44, 44, 44, 44, 44, 44, 44, 48, 48, 48, 48, 48, 48, 48, 48, 52, 52, 52, 52, 52, 52, 52, 52, 56, 56, 56, 56, 56, 56, 56, 56, 60, 60, 60, 60, 60, 60, 60, 60, 64, 64, 64, 64, 64, 64, 64, 64, 68, 68, 68, 68, 68, 68, 68, 68, 72, 72, 72, 72, 72, 72, 72, 72, 76, 76, 76, 76, 76, 76, 76, 76, 80, 80, 80, 80, 80, 80, 80, 80, 84, 84, 84, 84, 84, 84, 84, 84, 88, 88, 88, 88, 88, 88, 88, 88, 92, 92, 92, 92, 92, 92, 92, 92, 96, 96, 96, 96, 96, 96, 96, 96, 97, 99 };

Hard to tell
Every time the number is considered, it is important to avoid the number to be added more than once.

For example, [1, 7, 4, 5],
dp[1] = true, since first number 1 is in the array;
dp[7] = true, since 7 is the second number in the array;
Also dp[8] should be true, since 1 + 7 = 8.
Next it is to work on index = 2, value 4,
dp[5] should be true, since 1 + 4 = 5, but it should not be updated right away.
The for loop in the following code is to iterate from 1 to 8.
Avoid setting dp[5 + 4] = 9.

Let me try to explain what it is wrong in the following statements:

for (int j = 1; j <= prefixSum; j++)
{
	if (dp[j])
    {
        dp[j + current] = true; 
    }
}

The reason to set dp[9] = true is that dp[5] is set true right away, and then dp[5] + 4 = 9, but 4 is counted twice.

The following code has a bug but I could not tell in my mock interview. I spent over 5 minutes to think but failed to come out the idea.

The correct solution
The working solution is here.

The following code has a bug, could not pass online judge. But I like to remind myself to be humble, and will figure out how to avoid the bug quickly.

public class Solution {
     public bool CanPartition(int[] nums) {
            if(nums == null || nums.Length == 0)
                return false; 
        
            var length = nums.Length; 
            var sum = nums.Sum(); 
        
            if(sum % 2 == 1)                
                return false; 
         
            var target = sum / 2; 
        
            var dp = new bool[sum + 1]; // target + 1 optimal
        
            Array.Sort(nums);            

            var prefixSum = 0; 
            for(int i = 0; i < nums.Length; i++)
            {
                var current = nums[i];                

                for (int j = 1; j <= prefixSum; j++)
                {
                    if (dp[j])
                    {
                        dp[j + current] = true; 
                    }
                }

                dp[current] = true;
                
                prefixSum += current;

                if (dp[target])
                    return true; 
            }

            return dp[target];
        }
}