C# DP Solution


  • 0
    D
    public class Solution {
       public bool CanPartition(int[] nums) {        
        int sum = 0;
        foreach(int i in nums)
        {
            sum += i;
        }
        
        if(sum %2 == 1) return false;
        return  ContainsSubsetWithSizeK(nums, sum/2);
    }
    
    private bool ContainsSubsetWithSizeK(int[] nums, int k)
    {
        bool[] dp = new bool[20000];
        for(int i=0; i < nums.Length; i++)
        {
            for(int j=dp.Length-1; j > 0; j--)
            {
                if(dp[j]) dp[j+nums[i]] = true; 
            }
            
            dp[nums[i]] = true;
        }
        
        return dp[k];
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.