Backtracking interview questions

Quick facts

Recall the answer first, then tap Show to check.

• itertools.permutationsShowHide

  permutations(xs) yields orderings in lexicographic order of positions, so sorted input gives sorted output.

• itertools.combinationsShowHide

  combinations(xs, k) yields every k-item selection in input order without repeats; there are n! / (k! (n - k)!) of them.

• itertools.productShowHide

  product("ab", repeat=3) yields all 2³ strings, the same as three nested loops.

• Copying the pathShowHide

  out.append(path[:]) stores a snapshot; appending path itself stores a reference that later changes.

• sys.setrecursionlimitShowHide

  Backtracking depth equals the number of choices in a path; it rarely nears CPython's default limit of 1000.