package leetcode;

/**
 * https://leetcode.com/problems/partition-equal-subset-sum/
 */
public class Problem416 {
    public boolean canPartition(int[] nums) {
        // TODO
        return false;
    }

    public static void main(String[] args) {
        Problem416 prob = new Problem416();
        System.out.println(prob.canPartition(new int[]{1, 5, 11, 5})); // true
        System.out.println(prob.canPartition(new int[]{1, 2, 3, 5})); // false
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -214,36 +214,168 @@
     
-// TODO%0A        return false
+int sum = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            sum += nums%5Bi%5D;%0A        %7D%0A        return canPartition(nums, sum, 0, 0, new HashMap%3C%3E())
 ;%0A  
@@ -388,21 +388,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -402,236 +402,594 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem416 prob = new Problem416();%0A        System.out.println(prob.canPartition(new int%5B%5D%7B1, 5, 11, 5%7D)); // true%0A        System.out.println(prob.canPartition(new int%5B%5D%7B1, 2, 3, 5%7D)); // false
+boolean canPartition(int%5B%5D nums, int sum, int idx, int accu,%0A                                        Map%3CInteger, Boolean%3E memo) %7B%0A        if (idx == nums.length) %7B%0A            if (accu == sum - accu) %7B%0A                return true;%0A            %7D%0A            return false;%0A        %7D%0A        if (memo.containsKey(accu)) %7B%0A            return memo.get(accu);%0A        %7D%0A        boolean found = false;%0A        found %7C= canPartition(nums, sum, idx + 1, accu + nums%5Bidx%5D, memo);%0A        found %7C= canPartition(nums, sum, idx + 1, accu, memo);%0A        memo.put(accu, found);%0A        return found;
 %0A   

Solve problem 416