How to Find All Subsets of an Array (Power Set)

A subset is any selection of elements from the array including the empty selection and the full array itself. For an array of size N, the total number of subsets is two raised to the power N. This is called the Power Set.

For every element in the array, you have exactly two choices. Either you include it in the current subset or you exclude it. Making this binary decision for every element and exploring all combinations generates the complete Power Set.

Create a recursive function that takes the current index, the current subset being built, the original array, and the results list. Start by calling it with index zero and an empty current subset.

At the beginning of each recursive call, add a copy of the current subset to the results list. This captures the subset at every possible stage of building, including the empty subset when no elements have been chosen yet.

Loop through the array starting from the current index. In each iteration, add the element at that index to the current subset. Recursively call the function with the next index. After the recursive call returns, remove the last element from the current subset. This is the backtracking step.

In the iterative approach, iterate through all numbers from zero to two raised to N minus one. Each number in binary represents a unique subset. If bit k of the current number is set to one, include element k from the array in the current subset. Otherwise exclude it.

The recursive backtracking approach is more intuitive and easier to extend for problems with constraints. The iterative bit manipulation approach is more compact. Both produce the same two to the power N subsets and have the same overall time complexity.