Recursion on Subsequences: Take vs. Skip
A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements (e.g., for `[1, 2]`, subsequences are `[]`, `[1]`, `[2]`, `[1, 2]`).
To generate all subsequences recursively, we make a **binary choice** at each index:
- Choice 1 (Take): Include the element at the current index in the active subsequence, and call the function recursively for the next index.
- Choice 2 (Skip/Backtrack): Remove the element from the active subsequence (backtrack), and call the function recursively for the next index.
- Base Case:
index === arr.length. When we've made decisions for all elements in the array, we print/save the current subsequence and return.
Complexity Analysis
Time Complexity: O(2^N)
Since we make 2 choices for each of the $N$ elements, the recursion tree has a branching factor of 2 and depth $N$, resulting in $2^N$ leaf nodes/subsequences.
Space Complexity: O(N)
The maximum height of the recursion tree and call stack depth is $N$, corresponding to the number of elements. Thus, auxiliary stack space is linear, $O(N)$.