To list every k-person roster from n engineers, how do include-exclude and index-loop recursions differ?

## Two trees, one output set You need every possible on-call roster of `k` engineers drawn from a team of `n`. There are two standard recursive shapes, and a good interview answer is that they are interchangeable in *what* they produce and very different in *how much work* they do to produce it. **Include-exclude.** Process engineers in a fixed order. At engineer `i`, branch twice: one child adds them to the roster and moves to `i+1`, the other skips them and moves to `i+1`. Emit when the roster reaches size `k`; stop when you run past the last engineer. This is a binary tree of depth `n`. Unpruned it has on the order of 2^n nodes regardless of how small `k` is, because it insists on making a decision about every engineer on every path. **Index-loop.** Carry a start index. Loop `i` from `start` to the end, add engineer `i`, recurse with start `i+1`, remove them. Emit when the roster reaches size `k`. This is a tree of depth `k` with a fan-out that shrinks as the start index advances. Every node corresponds to a strictly increasing sequence of indices — that is, a valid partial roster — and the `i+1` is what enforces "no repeats and no reordering", which is the whole reason rosters are not counted twice. The increasing-index invariant is the conceptual heart of the index-loop form. Rosters are unordered, so of the many orders in which a given group could be picked, the search allows exactly one: the increasing one. That is the same canonical-choice trick that shows up whenever you need to enumerate sets rather than sequences. ## Where the pruning hangs Neither shape is efficient without a feasibility test. If you have chosen `c` members and there are `r` engineers left unconsidered, and `c + r < k`, this branch can never complete and every node below it is wasted. | | include-exclude | index-loop | |---|---|---| | depth | n | k | | branching | 2, constant | shrinks with start index | | every node valid? | no, many can never reach k | yes, every node is a valid prefix | | where the prune lives | explicit test, usually on the exclude branch | the loop's upper bound | | natural extension | more than two states per item | allowing repeats, by recursing with i | In the index-loop version the prune is expressed by stopping the loop early rather than running it to the last index: once fewer engineers remain than slots to fill, the remaining iterations are all doomed. Writing the loop to the end and relying on the base case to reject is the single most common inefficiency in this family, and it is invisible in output — you get the right rosters, just after touching far more nodes than necessary. Include-exclude also gets a cheap win from emitting and returning the moment the roster hits size `k`, instead of descending through the remaining engineers taking the exclude branch every time. With both prunes in place the two shapes end up doing comparable work; without them, include-exclude is the one that blows up. ## When each shape is the right reach Reach for the **index-loop** when `k` is much smaller than `n` and the selection is a plain "choose some". The depth is `k`, the nodes are all useful, and the code has one loop and one recursion. This is the default. Reach for **include-exclude** when the per-item decision is the natural unit: - Each item has more than two outcomes — not just in or out, but in as primary, in as backup, or out. The binary tree generalises to a tree with one branch per state; the index-loop does not generalise as cleanly. - The decision at item `i` depends on a running quantity rather than on position — a budget consumed, a capacity used. Include-exclude makes that quantity a natural parameter of the recursion. - You want every roster size at once rather than exactly `k`. Drop the size test and every leaf is an answer, which is the same shape as full subset enumeration. ## The variant that changes the output One small edit to the index-loop changes the problem: recurse with `i` instead of `i+1`, and the current engineer stays available. The invariant relaxes from strictly increasing to non-decreasing, and you now enumerate selections that may repeat an item rather than plain rosters. That is worth knowing precisely because interviewers use it as a one-word follow-up — "what if someone can take two shifts?" — and the answer is a single character, not a rewrite. ## What is being tested This question is a template-versus-understanding probe. A candidate who has memorised one shape will insist the other is wrong or produces different results. A candidate who understands the search will say: same outputs, different trees, depth `k` versus depth `n`, and here is where each hangs the feasibility prune. That second answer is what you want to be able to give.