Given an array of distinct integers, return all of its subsets (the power set), in any order, without duplicates.
Before you code
There are 2ⁿ subsets, so any solution is at least O(2ⁿ). Decide whether to record a subset at every node of the search (the lesson's version) or only at the leaves of an include/exclude tree.
Hints
- Pass a
startindex so each call only adds numbers after the last one chosen; that is what prevents[2, 1]as well as[1, 2]. - Record a copy of the path, not the path itself.
- Alternative without recursion: for each mask from 0 to 2ⁿ − 1, the set bits choose the elements.
Production & complexity notes
When solving Subsets on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.