Java simple solution with a helper method


  • 0

    Here we use sum[s] to indicate whether sum s can be obtained.

        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int n : nums)
                sum += n;
            return sum % 2 == 0 && canPartition(sum / 2, nums);
        }   
    
        static boolean canPartition(int target, int[] nums) {
            boolean sum[] = new boolean[target + 1]; // sum[s] := true if s can be a sum
            sum[0] = true;
            for (int n : nums)
                for (int s = target; s >= n; s--)
                    if (sum[s - n]) 
                        sum[s] = true;
            return sum[target];
        } 
    

Log in to reply
 

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