78. Subsets | Time: O (n*2^n) | Space: O (n*2^n)

// Problem: https://leetcode.com/problems/subsets/
// Solution: https://www.algoexpert.io/questions/Powerset

import java.util.ArrayList;

class Program {
  // O(n*2^n) time | O(n*2^n) space
  public static ArrayList<ArrayList<Integer>> powerset(ArrayList<Integer> array) {
    return powerset(array, array.size() - 1);
  }

  public static ArrayList<ArrayList<Integer>> powerset(ArrayList<Integer> array, int idx) {
    if (idx < 0) {
      ArrayList<ArrayList<Integer>> emptySet = new ArrayList<ArrayList<Integer>>();
      emptySet.add(new ArrayList<Integer>());
      return emptySet;
    }

    int ele = array.get(idx);
    ArrayList<ArrayList<Integer>> subsets = powerset(array, idx - 1);
    int length = subsets.size();
    for (int i = 0; i < length; i++) {
      ArrayList<Integer> currentSubset = new ArrayList<Integer>(subsets.get(i));
      currentSubset.add(ele);
      subsets.add(currentSubset);
    }
    return subsets;
  }
}