Subsets

Subsets

What is this problem about?

The "Subsets" problem is a fundamental backtracking challenge. Given an array of unique integers, you need to return all possible subsets (the power set). A subset is any combination of elements from the original array, including the empty set and the array itself. For an array of size n, there are always 2^n possible subsets. The order of the subsets in the output does not matter.

Why is this asked in interviews?

This is a core question asked by almost every major tech company, including Apple, Amazon, and Google. It is the definitive test of a candidate's understanding of Backtracking and Recursion. It evaluates whether you can visualize a decision tree—where at each step you either include an element in your subset or you don't. It's a baseline requirement for roles involving algorithm development.

Algorithmic pattern used

The problem is typically solved using Backtracking or Bit Manipulation.

• Backtracking: You use a recursive function that explores two branches for each element: one where the element is added to the current subset, and one where it is skipped. This builds the decision tree until all elements have been considered.
• Bit Manipulation: Since there are 2^n subsets, you can iterate from 0 to 2^n - 1. Each number's binary representation tells you which elements to include in the subset (e.g., if the 3rd bit is 1, include the 3rd element).

Example explanation (use your own example)

Array: [1, 2]

1. Start with an empty subset: [].
2. Consider 1:
   • Branch A: Include 1 -> [1]
   • Branch B: Skip 1 -> []
3. Consider 2 for both branches:
   • From [1]: Include 2 -> [1, 2], Skip 2 -> [1]
   • From []: Include 2 -> [2], Skip 2 -> [] Final result: [[], [1], [2], [1, 2]].

Common mistakes candidates make

The most common mistake is failing to "backtrack" properly—forgetting to remove an element from the current path before returning from a recursive call. Another mistake is not creating a deep copy of the subset before adding it to the result list, which results in a list of empty arrays (since the original array is eventually cleared). Candidates also sometimes struggle to explain the 2^n time complexity.

Interview preparation tip

To excel in the Subsets interview pattern, draw out the recursion tree for a small example like [1, 2, 3]. Visualizing how the code "moves" through the tree will help you explain it more clearly. Also, be ready to discuss the Bit Manipulation approach as an alternative, as it demonstrates a different but equally valid mental model.