Leetcode discuss: 416. Partition Equal Subset Sum

 Here is the link. 

Second practice - C# - Next round - avoid adding more than once

Dec. 29, 2020
Introduction
I wrote a solution but failed at next to last test case. I debugged the code and then figured out that same number in the array is added more than once. After my first failed practice, I started to work on bug fix.

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

Working solution
I made the code change, use HashSet to store the new updated value first, and then update dp[] array in the last.

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

                // hard to figure out - only add once - this bug 
                var nextRound = new HashSet<int>(); 
                for (int j = 1; j <= prefixSum; j++)
                {
                    if (dp[j])
                    {
                        nextRound.Add(j + current); 
                    }
                }

                foreach (var item in nextRound)
                {
                    dp[item] = true; 
                }

                dp[current] = true;

                prefixSum += current;

                if (dp[target])
                    return true; 
            }

            return dp[target];
        }
}