Advertisement
rishu110067

Untitled

Jan 17th, 2022
554
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Result {
  2.     public static boolean helper(int idx, List<Integer> s, List<Boolean> slate, int sumGroup1, int sumGroup2, List<Boolean> results){
  3.        
  4.         if(idx == s.size()){    // base case
  5.             if(sumGroup1 == sumGroup2 && slate.stream().distinct().count() > 1){
  6.                 results.addAll(slate);
  7.                 return true;
  8.             }
  9.         }
  10.         else{   // recursive case
  11.             // include in group 1
  12.             slate.add(true);
  13.             if(helper(idx+1,  s, slate, sumGroup1+s.get(idx), sumGroup2, results)){
  14.                 return true;
  15.             }
  16.             slate.remove(slate.size()-1);
  17.  
  18.             // exclude from group 1 / include in group 2
  19.             slate.add(false);
  20.             if(helper(idx+1,  s, slate, sumGroup1, sumGroup2+s.get(idx), results)){
  21.                 return true;
  22.             }
  23.             slate.remove(slate.size()-1);
  24.         }
  25.         return false;
  26.     }
  27.  
  28.     public static List<Boolean> equalSubSetSumPartition(List<Integer> s) {
  29.         List<Boolean> results = new ArrayList<>();
  30.         Boolean[] dp = new Boolean[s.size()+1];
  31.         helper(0, s, new ArrayList<>(), 0, 0, results);
  32.         // System.out.println(results);
  33.         return results;
  34.     }
  35. }
  36.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement