/*

Write a function that takes in an array of unique integers and returns its powerset.

Sample Input : [1, 2, 3]

Output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Explanation:

The code snippet represents a function `Powerset` that takes an array of integers as input and returns the powerset

of the array. The powerset of a set is the set of all possible subsets of that set, including the empty set and the set itself.

The function `Powerset` calls a helper function `powerset` to perform the actual computation. Here's how the code works:

1. The `Powerset` function initializes the computation by calling the `powerset` function with the array and the index

of the last element in the array (`len(array) - 1`).

2. The `powerset` function is a recursive function that calculates the powerset. It takes the array and the current

index as input.

3. At each recursive call, the function checks if the index is less than 0. If so, it means all elements have been

processed, and it returns a 2D slice containing the empty set as the only subset.

4. If the index is not less than 0, the function retrieves the element at the current index from the array.

5. The function recursively calls itself with the array and the index decremented by 1 to generate the subsets without

the current element.

6. It then calculates the length of the subsets generated so far.

7. Using a loop, the function iterates over the existing subsets and creates new subsets by appending the current element

to each subset. The new subsets are added to the existing subset slice.

8. Finally, the function returns the updated subset slice, which contains all the subsets of the original array.

By recursively generating subsets while building upon the subsets generated at each step, the function constructs the

powerset of the given array.

O(n*2^n) time | O(n*2^n) space - where n is the length of the input array

*/

import java.util.ArrayList;

import java.util.List;

class Main {

public static List<List<Integer>> powerset(int[] array, int index) {

// Base case: when the index reaches -1, return a list with an empty subset

if (index < 0) {

List<List<Integer>> subsets = new ArrayList<>();

subsets.add(new ArrayList<>());

return subsets;

}

int element = array[index];

// Recursive call to generate the powerset for the elements up to index - 1

List<List<Integer>> subsets = powerset(array, index - 1);

// Length of the current subsets list

int length = subsets.size();

// Iterate through each subset and create new subsets by adding the current element

for (int i = 0; i < length; i++) {

List<Integer> currentSubset = subsets.get(i);

// Create a new subset by making a copy of the current subset

List<Integer> newSubset = new ArrayList<>(currentSubset);

// Add the current element to the new subset

newSubset.add(element);

// Add the new subset to the existing subsets list

subsets.add(newSubset);

}

// Return the resulting subsets list

return subsets;

}

public static List<List<Integer>> powerset(int[] array) {

// Call the helper function to generate the powerset starting from the last index

return powerset(array, array.length - 1);

}

public static void main(String[] args) {

int[] array = {1, 2, 3};

List<List<Integer>> subsets = powerset(array);

// Print the subsets

for (List<Integer> subset : subsets) {

System.out.println(subset);

}

}

}

// Iterative approach

public class Powerset {

public static List<List<Integer>> powerset(int[] array) {

List<List<Integer>> subset = new ArrayList<>();

subset.add(new ArrayList<>()); // Initialize the powerset with the empty subset

// Iterate over each element in the input array

for (int ele : array) {

int length = subset.size(); // Get the current length of the subset

// Iterate over each existing subset

for (int i = 0; i < length; i++) {

List<Integer> currentSubset = new ArrayList<>(subset.get(i)); // Get the current subset

// Create a new subset by making a copy of the current subset

List<Integer> newSubset = new ArrayList<>(currentSubset);

// Add the current element to the new subset

newSubset.add(ele);

// Append the new subset to the powerset

subset.add(newSubset);

}

}

// Return the powerset

return subset;

}

public static void main(String[] args) {

int[] array = {1, 2, 3};

List<List<Integer>> result = powerset(array);

System.out.println(result);

}

}