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) {
    ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
    subsets.add(new ArrayList<Integer>());
    for (Integer ele : array) {
      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;
  }
}