Subsets

Backtracking · Bitmask · Power Set

1:00

Three ways to generate the complete power set of a set — backtracking, bitmask enumeration, and cascading — and why any method costs O(n · 2ⁿ).

By the end, you can

Explain why n distinct elements produce exactly 2ⁿ subsets.
Trace the backtracking algorithm on a small input and identify each choose, explore, and un-choose step.
Convert a bitmask integer to the corresponding subset and vice versa.
Describe the cascading algorithm and explain why it produces 2ⁿ subsets after processing all n elements.
State the time and space complexity of power-set generation and justify the O(n) per-subset factor.
Distinguish subsets from permutations and explain why order is irrelevant.
Modify the backtracking solution to handle duplicate elements (Subsets II).

Up next in Coding Interview Patterns