How big is the search space?

Backtracking Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from math import comb, factorial
print(2 ** 20, factorial(10), comb(20, 10))

Options

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

Show answer

Answer: A 1048576 3628800 184756

Right: these three are the usual 'still fine' sizes for listing.

Knowing these magnitudes lets you judge in seconds whether listing everything fits a time limit.

Why not the others?
  • B 1048576 362880 184756. That is 9!, not 10!.
  • C 1000000 3628800 184756. 2²⁰ is a little over a million.

30-second answer

Count the leaves of the decision tree: two choices per item gives 2ⁿ, choosing an order gives n!, k choices per position over L positions gives kᴸ. Multiply by the work per leaf (often O(n) to copy). As a rough guide, 2²⁰ is about a million and 10! is about 3.6 million, so n around 20 for selections and around 10 for orderings is the practical limit.

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

Explain how to estimate a search space.

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

  • Leaves of the decision tree
  • 2ⁿ, n!, kᴸ
  • Practical limits

Deep dive

The input limits in a question often reveal the intended approach: n ≤ 20 hints at 2ⁿ.

If the output itself is exponential, no algorithm can be faster than writing it.

Meet in the middle splits 2ⁿ into two 2^(n/2) halves for some sum questions.

Common mistakes

  • Treating 2⁴⁰ as feasible.
  • Forgetting the per-leaf copy cost.

Senior take & follow-ups

Quote the rough sizes (2²⁰, 10!) when you justify an approach.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is meet in the middle?

    Show hint

    Enumerate sums of each half separately, sort one, and binary search for complements: O(2^(n/2) · n).

  2. How do you spot that DP will work instead?

    Show hint

    The state that matters (remaining total, position) has few distinct values.

Similar on Backend: Back-of-the-envelope estimates The Backend page estimates traffic and storage for a system; this page estimates how many branches a search will visit.

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.