Every order of a playlist

Backtracking Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

path, out = [], []
for a in [1, 2]:
    path.append(a)
    out.append(path)
    path.pop()
print(out)

Options[[], []][[1], [2]][1, 2]

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

Show answer

Answer: A [[], []]

Right: both entries are the same list object, which is empty after the pops.

Recording path[:] stores a snapshot, which is the one-character difference between right and wrong answers here.

Why not the others?

B [[1], [2]]. No copy was taken, so the entries share one list.
C [1, 2]. out holds lists, not numbers.

30-second answer

Build orderings one position at a time: try each unused song in the next slot, recurse, then undo. Sorting the ids first makes the output come out in sorted order with no extra sort. There are n! orderings of length n, so O(n · n!) time is the best possible. Apart from the output, the path and flags take O(n) space.

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

Explain listing every ordering.

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

Pick an unused item per slot
Undo after recursing
O(n · n!)

Deep dive

The 'used' flags plus undo are the template for every ordering question.

Swapping items in place avoids the flag list but produces a different output order.

With repeated ids, skip a value equal to the previous one when that previous one is unused.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def all_orders(songs: list[int]) -> list[list[int]]:
    songs = sorted(songs)
    used = [False] * len(songs)
    path: list[int] = []
    out: list[list[int]] = []

    def place() -> None:
        if len(path) == len(songs):
            out.append(path[:])  # snapshot, not the live list
            return
        for i, s in enumerate(songs):
            if not used[i]:
                used[i] = True
                path.append(s)
                place()
                path.pop()  # undo before trying the next song
                used[i] = False

    place()
    return out

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun allOrders(songs: List<Int>): List<List<Int>> {
    val items = songs.sorted()
    val used = BooleanArray(items.size)
    val path = mutableListOf<Int>()
    val out = mutableListOf<List<Int>>()
    fun place() {
        if (path.size == items.size) {
            out.add(path.toList()) // snapshot, not the live list
            return
        }
        for ((i, s) in items.withIndex()) {
            if (used[i]) continue
            used[i] = true
            path.add(s)
            place()
            path.removeLast() // undo before the next song
            used[i] = false
        }
    }
    place()
    return out
}

Common mistakes

Appending path instead of a copy, so every answer ends up empty.
Forgetting to reset the used flag after the recursive call.

Senior take & follow-ups

Mention that output size bounds the cost; it shows you know you cannot beat n!.

Follow-up questions

Think of your answer first, then open the hint.

How many orderings does 10 songs give?
Show hint
10! = 3,628,800; more than about 11 is usually too many to list.
How do you get the next ordering without listing all?
Show hint
Find the rightmost rise, swap with the next larger value to its right, and reverse the tail.

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.