Introduction

To generate all possible ways values can be removed from a sequence, you first need to clarify what "way" means. If any subset of positions may be removed, the result set is the set of all subsequences, and there are 2^n of them for a sequence of length n. If only contiguous blocks may be removed, that is a different and much smaller problem. Most versions of this question mean arbitrary removals while preserving the order of the surviving elements.

The Core Combinatorial Fact

For each position in the sequence, you have two choices:

• keep it
• remove it

Those independent binary choices produce 2^n possible outcomes. That count includes:

• removing nothing
• removing everything
• every partial removal pattern in between

So there is no algorithm that lists all results faster than exponential time in the worst case, because the output itself is exponential.

That is the first thing to understand: once you ask for all possibilities, O(2^n) output is unavoidable.

Generate Them with Backtracking

A clean way to enumerate every result is backtracking. At each index, recurse twice: once keeping the current value and once removing it.

1from typing import List, Any
2
3
4def all_removals(seq: List[Any]) -> List[List[Any]]:
5    result = []
6    current = []
7
8    def dfs(i: int) -> None:
9        if i == len(seq):
10            result.append(current.copy())
11            return
12
13        current.append(seq[i])
14        dfs(i + 1)
15        current.pop()
16
17        dfs(i + 1)
18
19    dfs(0)
20    return result
21
22
23print(all_removals(["a", "b", "c"]))

This returns:

[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]

Each returned sequence corresponds to one removal pattern.

Track the Removed Positions Explicitly

Sometimes you do not want only the remaining sequence. You want to know which positions were removed.

That version is only a small variation:

1from typing import List, Tuple
2
3
4def removal_patterns(seq: List[int]) -> List[Tuple[List[int], List[int]]]:
5    result = []
6    kept = []
7    removed = []
8
9    def dfs(i: int) -> None:
10        if i == len(seq):
11            result.append((kept.copy(), removed.copy()))
12            return
13
14        kept.append(seq[i])
15        dfs(i + 1)
16        kept.pop()
17
18        removed.append(i)
19        dfs(i + 1)
20        removed.pop()
21
22    dfs(0)
23    return result
24
25
26for kept_values, removed_positions in removal_patterns([10, 20, 30]):
27    print("kept=", kept_values, "removed_positions=", removed_positions)

This is useful when two different removal choices can produce the same remaining values, especially if the sequence contains duplicates.

Handling Duplicate Values

If the sequence has repeated values, distinct removal patterns can lead to the same resulting sequence.

Example:

• remove the first a from [a, a, b]
• remove the second a from [a, a, b]

Both yield [a, b], but they are different removal choices.

So decide early whether you need:

• all removal patterns by position
• all distinct resulting sequences

If you need only distinct resulting sequences, collect them in a set:

1
2def distinct_results(seq):
3    return {tuple(result) for result in all_removals(seq)}
4
5
6print(distinct_results(["a", "a", "b"]))

That deduplicates outcomes while still using the same underlying generation logic.

If the Removal Must Be Contiguous

Some interview versions of the problem mean removing one contiguous block instead of any subset of positions. That problem is much smaller.

For a sequence of length n, every contiguous removal is determined by a start and end index. That gives O(n^2) possibilities rather than O(2^n).

1
2def remove_one_contiguous_block(seq):
3    result = []
4    n = len(seq)
5    for start in range(n + 1):
6        for end in range(start, n + 1):
7            result.append(seq[:start] + seq[end:])
8    return result
9
10
11print(remove_one_contiguous_block([1, 2, 3]))

This is a different problem from arbitrary removals, and it is worth stating that explicitly when clarifying the requirement.

Choose the Representation That Matches the Real Goal

Before coding, decide whether the caller actually needs:

• every remaining sequence
• every set of removed positions
• only the count of possibilities
• only distinct results

That choice affects memory usage and complexity much more than the recursion itself.

For example, if the caller needs only the number of possible arbitrary removals, the answer is simply 2^n, and you should not generate anything.

Common Pitfalls

The biggest mistake is ignoring the output size. If you ask for all arbitrary removal patterns, exponential growth is unavoidable.

Another mistake is failing to define whether duplicate outcomes should appear once or multiple times. With repeated values, that matters immediately.

Developers also often blur the difference between arbitrary removals and contiguous-block removals. Those are different problems with very different complexity.

Finally, avoid building the whole result set in memory if the sequence is large. A generator-based approach may be better when callers can stream the outputs.

Summary

• Arbitrary removals from a sequence correspond to all subsequences, so there are 2^n outcomes.
• Backtracking is a clean way to enumerate every removal pattern.
• Track removed positions explicitly when duplicate values make outcomes ambiguous.
• If the task is actually contiguous-block removal, the problem drops to O(n^2) possibilities.
• Clarify the exact requirement before optimizing the algorithm.