DFS Thinking Model

Depth‑first search (DFS) is the foundation for solving problems that involve exploring possibilities: paths in a graph, subsets, permutations, valid parentheses, and more.

The key is to see the problem as a tree of decisions, and then write a DFS that walks this tree systematically.

From Problem to Decision Tree

Most DFS / backtracking problems share three elements:

1. State – where you are in the decision process.
2. Choices – what options you have from this state.
3. Constraints / goal – when a path is valid and when to stop.

For example, generating all subsets of a set:

• State: which index i we are at, and which elements we’ve picked so far.
• Choices: at each i, either include or exclude nums[i].
• Goal: when i == n, record the current subset.

Visualize it as a binary tree where each level corresponds to an index.

Generic DFS + Backtracking Template

For recursive DFS on combinatorial problems, a common template is:

JavaCopy
void dfs(State state) {
    if (isComplete(state)) {
        recordAnswer(state);
        return;
    }

    for (Choice choice : choicesFrom(state)) {
        apply(choice, state);      // make a decision
        dfs(state);                // recurse
        undo(choice, state);       // backtrack
    }
}

Key ideas:

• apply → recurse → undo is the backtracking pattern.
• State is often represented implicitly with parameters + a few data structures.

Typical DFS Use Cases

• Generate all:
  • Subsets / combinations.
  • Permutations.
  • Valid parentheses strings of length 2n.
• Constrained paths:
  • Word ladders (DFS version), grid paths, robot moves with obstacles.
• Graph traversal:
  • Connected components, topological sort (with care), cycle detection.

In interviews, as soon as you see “generate all X” or “count all valid X” with clear constraints, DFS / backtracking should be high on your list.

Choosing State and Recursion Parameters

Good DFS solutions usually have minimal and clear state:

• An index i (position in array / string).
• A partial result (path, current, stack).
• Any extra information needed to enforce constraints (e.g. remaining counts, last value).

Example for permutations:

• Parameters: path (list of chosen numbers), used[] (bool array).
• Base case: path.size() == n → record path.
• Choices: for each index i not used, choose nums[i], mark used, recurse, then unmark.

This leads to a clean, symmetric recursion.

When to Prune (Backtracking)

Backtracking is simply pruning impossible or unpromising branches early:

• If a partial path already violates constraints (e.g. sum exceed target, invalid prefix), return immediately.
• If you can prove that no extension of the current state can lead to a better answer, stop.

Examples:

• N‑Queens: as soon as a queen conflicts (same column / diagonal), stop exploring that branch.
• Parentheses generation: never allow more ')' than '(' at any prefix.

Effective pruning often makes exponential problems tractable on interview‑sized inputs.

DFS vs BFS

Aspect	DFS	BFS
Order	Go deep along one path	Explore level by level
Use cases	All possibilities, backtracking, paths	Shortest path (unweighted), levels
Memory	Up to recursion depth	Up to width of the frontier

If you specifically need shortest number of steps, reach for BFS.
If you need to explore the whole search space with constraints, DFS + backtracking is the more natural choice.

Common Pitfalls

• Missing base case or placing it incorrectly.
• Forgetting to undo changes when unwinding recursion.
• Reusing mutable objects (like lists) without copying when recording an answer.
• Exponential blowup due to lack of pruning when constraints clearly allow it.

When debugging, print the current state at each recursion entry and exit; you’ll quickly see whether your apply/undo logic is symmetric and correct.

How to Practice DFS Thinking

1. Start with classic problems:
   • Subsets, permutations, combinations, parentheses.
2. For each, write down:
   • State, choices, constraints, base case.
3. Then move to graph problems:
   • Connected components, path existence, cycle detection.

The more trees of decisions you draw on paper, the more natural DFS will feel. Over time, you’ll see that many different problems share the same DFS skeleton, just with different states and constraints.