Easy subset sum beats 90%


  • 0
    U
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for(int n : nums) {
                sum += n;
            }
            if(sum % 2 != 0) return false;
            
            int target = sum / 2;
            boolean dp[] = new boolean[target + 1];
            dp[0] = true;
            for(int n : nums) {
                for(int i = target; i >= n; i--) {
                    if(dp[i-n]) dp[i] = true;
                }
            }
            return dp[target];
        }
    

Log in to reply
 

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