# Untitled

Jan 18th, 2022
737
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Result {
2.     /**
3.      * Bottom-up DP solution
4.      */
5.     public static List<Boolean> equalSubSetSumPartition(List<Integer> s){
6.         /**
7.          * Steps:
8.          * - check if the total sum is even or not - can't be odd to find a solution
9.          * - targetSum is the total/2
10.          * - 2D dp array -> dp[idx][sum]
11.          * - base cases:
12.          *      - when idx = 0 to n and sum = 0 -> dp[0..n][0] = 0
13.          */
14.         // get targetSum
15.         int total = 0, sum_neg = 0, sum_pos = 0;
16.         for(int val: s){
17.             total += val;
18.             if(val < 0) sum_neg += val;
19.             else sum_pos += val;
20.         }
21.         if(total % 2 != 0){
22.             return new ArrayList<>(); // no solution if total is not an even number
23.         }
24.         int targetSum = total / 2;
25.
26.         Map<List<Integer>, Boolean> dp = new HashMap<>();
27.
28.         for(int idx=0; idx<s.size(); idx++){
29.             for(int sum=sum_neg; sum<=sum_pos; sum++){
30.                 if(sum==s.get(idx)){ // base case
31.                     dp.put(Arrays.asList(idx, sum), true);
32.                 }
33.                 else if(idx==0){ // base case
34.                     dp.put(Arrays.asList(idx, sum), false);
35.                 }
36.                 else {
37.                     Boolean exclude = dp.get(Arrays.asList(idx-1, sum));
38.                     Boolean include = dp.get(Arrays.asList(idx-1, sum-s.get(idx)));
39.                     // include can be null when dp doesn't contain the key
40.                     if(include == null) include = false;
41.                     dp.put(Arrays.asList(idx, sum), exclude || include);
42.                 }
43.             }
44.         }
45.         // Return empty list if it's not possible to partition into equal sum sets
46.         if(dp.get(Arrays.asList(s.size()-1, targetSum)) == false) {
47.             return new ArrayList<>();
48.         }
49.
50.         List<Boolean> slate = new ArrayList<>();
51.         int idx = s.size()-1, sum = targetSum;
52.         while(idx >= 0)
53.         {
54.             if(sum == s.get(idx)) {
56.                 sum -= s.get(idx);
57.                 idx--;
58.                 while(idx >= 0) {
60.                     idx--;
61.                 }
62.                 break;
63.             }
64.
65.             Boolean exclude = dp.get(Arrays.asList(idx-1, sum));
66.             Boolean include = dp.get(Arrays.asList(idx-1, sum-s.get(idx)));
67.             // include can be null when dp doesn't contain the key
68.             if(include == null) include = false;
69.             if(exclude) {
71.                 idx--;
72.             }
73.             else {
75.                 sum -= s.get(idx);
76.                 idx--;
77.             }
78.         }
79.         // Return empty list if all the elements of slate are the same
80.         if(slate.stream().distinct().count() == 1) {
81.             return new ArrayList<>();
82.         }
83.
84.         // need to reverse the slate as we found the slate going backward
85.         Collections.reverse(slate);
86.         return slate;
87.     }
88. }
89.
90.