Just use the exactly same method with "Balanced Partition" problem.


  • 0

    Here is a great tutorial: Balanced Partition.

    public class Solution {
        public boolean canPartition(int[] nums) {
            int s = 0;
            for (int n:nums) {
                s += n;
            }
            if ((s & 1) == 1) return false;
            s /= 2;
            boolean[][] p = new boolean[nums.length + 1][s + 1];
            for (int i = 0; i <= nums.length; i++) {
                p[i][0] = true;
            }
            for (int i = 1; i <= nums.length; i++) {
                for (int j = s; j >= nums[i - 1]; j--) {
                    if (p[i-1][j] || p[i-1][j-nums[i-1]]) p[i][j] = true;
                }
            }
            return p[nums.length][s];
        }
    }
    

Log in to reply
 

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