content: package math;
  
  import java.util.ArrayList;
  import java.util.HashSet;
  import java.util.List;
  
  public class IntegerSubsets {
  
      /*
       * Find all subsets of a given set of integers
       * Input: {2, 3, 4}
       * Output: {}, {2}, {3}, {4}, {2,3}, {2,4}, {3,4}, {2,3,4}
       *
       * Runtime Complexity:
       * Exponential, O(2n) - where 'n' is number of integers in the given set.
       *
       * Memory Complexity:
       * Exponential, O(2n)
       *
       * n = size of given integer set
       * subsets_count = 2^n
       *  for i = 0 to subsets_count
       *      form a subset using the value of 'i' as following:
       *          bits in number 'i' represent index of elements to choose from original set,
       *          if a specific bit is 1 choose that number from original set and add it to current subset,
       *  e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
       *  add current subset to list of all subsets
       *
       * */
  
      private static int getBit(int num, int bit) {
          int temp = (1 << bit);
          temp = temp & num;
          if (temp == 0) {
              return 0;
          }
          return 1;
      }
  
      private static void getAllSubsets(List<Integer> v,
                                        List<HashSet<Integer>> sets) {
  
          int subsets_count = (int) (Math.pow((double) 2, (double) v.size()));
          for (int i = 0; i < subsets_count; ++i) {
              HashSet<Integer> set = new HashSet<Integer>();
              for (int j = 0; j < v.size(); ++j) {
                  if (getBit(i, j) == 1) {
                      int x = v.get(j);
                      set.add(x);
                  }
              }
              sets.add(set);
          }
      }
  
      public static void main(String[] args) {
          Integer[] arr = new Integer[]{8, 13, 3, 22, 17, 39, 87, 45, 36};
          List<Integer> v = new ArrayList<>();
          for (Integer i : arr) {
              v.add(i);
          }
  
          List<HashSet<Integer>> subsets = new ArrayList<>();
          getAllSubsets(v, subsets);
  
          for (int i = 0; i < subsets.size(); ++i) {
              System.out.print("{");
              for (Integer it : subsets.get(i)) {
                  System.out.print(it + ", ");
              }
              System.out.println("}");
          }
      }
  }
  