class Result {
    /**
     * Bottom-up DP solution
     */
    public static List<Boolean> equalSubSetSumPartition(List<Integer> s){
        /**
         * Steps:
         * - check if the total sum is even or not - can't be odd to find a solution
         * - targetSum is the total/2
         * - 2D dp array -> dp[idx][sum]
         * - base cases:
         *      - when idx = 0 to n and sum = 0 -> dp[0..n][0] = 0
         */
        // get targetSum
        int total = 0, sum_neg = 0, sum_pos = 0;
        for(int val: s){
            total += val;
            if(val < 0) sum_neg += val;
            else sum_pos += val;
        }
        if(total % 2 != 0){
            return new ArrayList<>(); // no solution if total is not an even number
        }
        int targetSum = total / 2;

        Map<List<Integer>, Boolean> dp = new HashMap<>();

        for(int idx=0; idx<s.size(); idx++){
            for(int sum=sum_neg; sum<=sum_pos; sum++){
                if(sum==s.get(idx)){ // base case
                    dp.put(Arrays.asList(idx, sum), true);
                }
                else if(idx==0){ // base case
                    dp.put(Arrays.asList(idx, sum), false);
                }
                else {
                    Boolean exclude = dp.get(Arrays.asList(idx-1, sum));
                    Boolean include = dp.get(Arrays.asList(idx-1, sum-s.get(idx)));
                    // include can be null when dp doesn't contain the key
                    if(include == null) include = false;
                    dp.put(Arrays.asList(idx, sum), exclude || include);
                }
            }
        }
        // Return empty list if it's not possible to partition into equal sum sets
        if(dp.get(Arrays.asList(s.size()-1, targetSum)) == false) {
            return new ArrayList<>();
        }

        List<Boolean> slate = new ArrayList<>();
        int idx = s.size()-1, sum = targetSum;
        while(idx >= 0)
        {
            if(sum == s.get(idx)) {
                slate.add(true);
                sum -= s.get(idx);
                idx--;
                while(idx >= 0) {
                    slate.add(false);
                    idx--;
                }
                break;
            }

            Boolean exclude = dp.get(Arrays.asList(idx-1, sum));
            Boolean include = dp.get(Arrays.asList(idx-1, sum-s.get(idx)));
            // include can be null when dp doesn't contain the key
            if(include == null) include = false;
            if(exclude) {
                slate.add(false);
                idx--;
            }
            else {
                slate.add(true);
                sum -= s.get(idx);
                idx--;
            }
        }
        // Return empty list if all the elements of slate are the same
        if(slate.stream().distinct().count() == 1) {
            return new ArrayList<>();
        }

        // need to reverse the slate as we found the slate going backward
        Collections.reverse(slate);
        return slate;
    }
}