Every selection from a set of toppings

Backtracking Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
items = [1, 2, 3]
out = []
for mask in range(1 << len(items)):
    pick = [x for i, x in enumerate(items) if mask >> i & 1]
    if len(pick) == 2:
        out.append(pick)
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [[1, 2], [1, 3], [2, 3]]

Right: masks 3, 5 and 6 have two bits set.

Each of the 2ⁿ masks is one selection, which is why the full listing costs O(n · 2ⁿ) however it is generated.

Why not the others?
  • B [[1, 2], [2, 3]]. Mask 5 picks 1 and 3.
  • C [[2, 1], [3, 1], [3, 2]]. Items are taken in list order.

30-second answer

Grow selections in sorted order: record the current path, then for each later item add it, recurse from the next index, and remove it. Every path is recorded once, giving all 2ⁿ selections with no repeats, already in sorted order. O(n · 2ⁿ) time to write them out. Apart from the output, the path takes O(n) space.

Practise saying it · 45 s. No recording, just a timer

Explain listing every selection.

Say your answer out loud, then check which of these points you covered:

  • Record each path
  • Loop from the next index
  • O(n · 2ⁿ)

Deep dive

Starting each loop after the last chosen index is what prevents repeats like [2, 1] after [1, 2].

The include-or-skip tree gives the same set in a different order.

Bitmasks from 0 to 2ⁿ - 1 list selections with no recursion.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def all_selections(toppings: list[int]) -> list[list[int]]:
    items = sorted(toppings)
    path: list[int] = []
    out: list[list[int]] = []

    def grow(start: int) -> None:
        out.append(path[:])  # every partial pick is an answer
        for i in range(start, len(items)):
            path.append(items[i])
            grow(i + 1)  # later items only, so no repeats
            path.pop()

    grow(0)
    return out

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun allSelections(toppings: List<Int>): List<List<Int>> {
    val items = toppings.sorted()
    val path = mutableListOf<Int>()
    val out = mutableListOf<List<Int>>()
    fun grow(start: Int) {
        out.add(path.toList()) // every partial pick is an answer
        for (i in start until items.size) {
            path.add(items[i])
            grow(i + 1) // later items only, so no repeats
            path.removeLast()
        }
    }
    grow(0)
    return out
}

Common mistakes

  • Starting the loop at 0, which produces repeats.
  • Recording only full-length paths.

Senior take & follow-ups

Name the start index as the 'no repeats' rule.

Follow-up questions

Think of your answer first, then open the hint.

  1. What changes if ids can repeat?

    Show hint

    Sort, then skip an item equal to the previous one at the same depth.

  2. How do you list only selections of size k?

    Show hint

    Record only when the path has k items, and stop growing past k.

What each operation costs: Depth First Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.