Standard Bar Recursion · Subsequences Pattern O(n * 2^n) — 2^n subsets, each copied in O(n) · O(n) recursion depth beyond the output
A charter operator lists candidate crew members and must file every possible roster — including the empty one — before the season starts. Each crew member is either on a roster or not, so the planner walks the list once and forks at every name: file the rosters that include this member, then the ones that don't. With all-distinct candidates, no two rosters coincide.
Input: An array nums of n distinct integers.
Output: All 2^n subsets, in the order the include-first depth-first walk emits them.
1 <= n <= 10-10 <= nums[i] <= 10all elements are distinctInput: {"nums":[1,2,3]}
Output: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
The include-first walk at index 0 emits every roster containing 1 before the rosters built from the rest; the empty roster lands last.
Input: {"nums":[0]}
Output: [[0],[]]
One member: take them, or file the empty roster.