Every Feature-Flag Combo
MediumBit Manipulation
Problem
A QA team wants to test every combination of the feature flags in flags (all names distinct). They number the combinations by a bitmask: combination m turns on flags[i] exactly when bit i of m is set.
Return all 2^n combinations ordered by m from 0 to 2^n - 1. Inside each combination, list the flags in their original order.
Example 1
- Input:
- flags = ["a", "b"]
- Output:
- [[], ["a"], ["b"], ["a", "b"]]
m = 0 (00), 1 (01), 2 (10), 3 (11).
Example 2
- Input:
- flags = ["x"]
- Output:
- [[], ["x"]]
Constraints
- 0 ≤ flags.length ≤ 12
- Flag names are distinct non-empty strings.
Hint
Show the first hint
There are exactly 2^n combinations, and the statement already gives each one a number.
Walkthrough
How to approach it
01Clarify before coding
- Is the empty combination included? Yes, it is m = 0 and always comes first.
- Does the order matter? Yes: by m, and flags inside each combination in input order, so the answer is unique.
- How large can n get? 12, so up to 4096 combinations.
02Brute force
Backtracking (include or skip each flag) produces every subset, but in a different order that then has to be re-sorted by its mask.
Cost: O(n · 2^n) to generate plus O(2^n log 2^n) to re-sort; the direct mask loop already produces the required order.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.