Advertisement
rishu110067

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)) {
  55.                 slate.add(true);
  56.                 sum -= s.get(idx);
  57.                 idx--;
  58.                 while(idx >= 0) {
  59.                     slate.add(false);
  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) {
  70.                 slate.add(false);
  71.                 idx--;
  72.             }
  73.             else {
  74.                 slate.add(true);
  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.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement