QuestionsDSA

Subsets (Power Set)

BacktrackingMediumDSA

Return all possible subsets of a set of distinct integers.

What it tests

The choose / recurse / un-choose skeleton.

Approach & answer

At each index you make a binary choice: include this number or not. Recurse, then remove it (backtrack) to explore the other branch. The path at every node is one subset — you record it on entry, not just at leaves, because every prefix is itself a valid subset. This choose→recurse→undo shape is every backtracking problem; the `start` index prevents revisiting earlier elements, so you generate combinations (not permutations). There are 2ⁿ subsets and copying each costs O(n), giving O(n·2ⁿ).

Use this technique when

'Generate all combinations/subsets' → build a partial solution, recurse, undo the last choice.

Complexity

Time O(n·2ⁿ) · Space O(n) recursion depth

References

js