DFSBackTracking

DFS / Backtracking

Depth-First Search (DFS), combined with backtracking, is an algorithmic technique used to explore all possible states by constructing partial solutions and undoing choices when needed. It is widely applied in enumeration, searching, and constraint-based problems.

When to Use DFS / Backtracking?

DFS is suitable for enumeration problems:

1. Combination Problems

Used to generate all possible subsets or combinations of items.
Examples include subsets, selecting k items, or finding combinations that sum to a target.

2. Permutation Problems

Used to generate all possible orderings of a set of numbers or characters.

Used to explore paths in trees, grids, or general graphs.
Examples include word search, flood fill, or root-to-leaf path enumeration.

Three Questions Before Writing DFS

1. Function Definition and Parameters

Clarify the state you need to maintain in recursion, such as index, path, sum, visited arrays, or grid position.

2. How to Break the Problem Into Subproblems

Decide what choices you can make at each recursive level: select an element, skip it, continue searching neighbors, or try candidates.

3. Base Case

Define when recursion should stop: target sum reached, full permutation formed, out of bounds in grid, or finishing an array.

LeetCode DFS / Backtracking Problem Introductions

78. Subsets

Generate the power set of a given list. Use DFS to either include or exclude each element.

90. Subsets II

Similar to Subsets, but the input contains duplicates. Use sorting and skip-duplicate logic.

77. Combinations

Generate all combinations of selecting k numbers from 1 to n. A classic level-based backtracking problem.

39. Combination Sum

Find all combinations that sum to a target where candidates can be reused. DFS explores repeated selections.

40. Combination Sum II

Each candidate can be used only once, and duplicates exist. Use sorting and skip repeated values.

216. Combination Sum III

Select exactly k numbers from 1 to 9 that sum to a target. Apply backtracking with pruning.

17. Letter Combinations of a Phone Number

DFS explores all possible letter mappings for each digit in the input string.

46. Permutations

Generate all permutations of a list using a visited array to track usage.

47. Permutations II

Permutations with duplicates. Sort first and skip equal values when the previous one is not used.

113. Path Sum II

Find all root-to-leaf paths in a binary tree that sum to a target. DFS handles the path construction.

DFS on a grid to check if a word exists by exploring four directions with visited marking.

733. Flood Fill

Standard DFS for filling connected regions in a grid.

212. Word Search II

A performance-heavy DFS problem requiring optimization such as Trie + DFS to search many words efficiently.

DFS Java Template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void dfs(int[] candidates, int startIndex, List<Integer> temp,
                List<List<Integer>> res, int currSum, int target) {

    if (currSum == target) {
        res.add(new ArrayList<>(temp)); // deep copy
        return;
    }

    if (currSum > target) {
        return;
    }

    for (int i = startIndex; i < candidates.length; i++) {
        int num = candidates[i];

        temp.add(num);

        // dfs(candidates, i) means reuse allowed
        // dfs(candidates, i + 1) means no reuse
        dfs(candidates, i, temp, res, currSum + num, target);

        temp.remove(temp.size() - 1);
    }
}