Backtracking

When should I use backtracking?

When the prompt asks for all of something: every subset, every ordering, every placement, every valid string. The output is exponential in the input, so no algorithm makes it cheap, and the skill is generating each candidate exactly once. The second signal is that a candidate is built from a sequence of small decisions, which is what lets you test a half-built candidate and abandon it early. If the prompt asks how many or which is best rather than list them all, look at dynamic programming first.

Why do I have to write res.append(path[:]) instead of res.append(path)?

Because every call shares one list. Appending path stores a reference to that same list, and the pops on the way back up empty it, so every answer you recorded turns into the empty list. This page runs that exact bug: on [1, 2, 3] the version without the copy returns eight empty lists instead of the eight subsets. The slice makes a snapshot that later pops cannot touch.

What is the difference between backtracking and DFS?

Backtracking is depth-first search over a tree of decisions rather than over a given graph, with two additions. The tree is generated as you walk it instead of existing beforehand, and the mark you make on the way down is undone on the way back up. Graph DFS leaves its visited set marked forever, because a node visited once never needs visiting again. Backtracking un-marks, because the same value may belong to a different branch.

When do I use a start index and when do I use a used set?

Use a start index when order does not matter, which covers subsets and combinations: passing start or i + 1 down means choices only ever move forward, so [1, 2] is generated and [2, 1] never is. Use a used set when order does matter, which is permutations: every unused element is a legal next choice at every level, and the set is what stops an element appearing twice in one candidate. For an input with repeated values, sort it first and skip a value equal to its left neighbour at the same level.

How do I state the complexity of a backtracking solution?

Count the leaves and multiply by the work per leaf. Subsets has 2^n leaves and copies a list of up to n elements at each, so it is O(n × 2^n). Permutations has n! leaves and the same copy, so O(n × n!). Say the number of candidates first, then the cost of emitting one, and say plainly that pruning does not change the bound but does change the constant, which on N-Queens is the difference between 341 calls and 17.