DFS & Backtracking — Explore All Possibilities

DFS goes deep before wide — perfect for "does a path exist", "count the islands", and the whole family of "generate all…" problems, where it wears its formal name: backtracking.

DFS on grids — flood fill / islands

function countIslands(grid) {
  let count = 0;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
    if (grid[r][c] !== "1") return;
    grid[r][c] = "0";                    // mark visited by sinking
    sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1);
  }
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++)
      if (grid[r][c] === "1") { count++; sink(r, c); }
  return count;
}

Each cell is visited once → O(rows × cols). "Number of Islands" is likely the single most-asked graph question in India's product-company interviews.

Backtracking — the choose / explore / unchoose template

// All permutations of nums
function permute(nums) {
  const res = [], path = [], used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      path.push(nums[i]); used[i] = true;    // 1. CHOOSE
      backtrack();                            // 2. EXPLORE
      path.pop();  used[i] = false;           // 3. UNCHOOSE (backtrack!)
    }
  }
  backtrack();
  return res;
}

That three-beat rhythm — choose, explore, unchoose — generates permutations, combinations, subsets, N-Queens, Sudoku solvers and word search. One template, a dozen classic problems: only the "choice" and the "goal" change.

Spot it when…

• "Generate ALL…" / "find every combination" → backtracking.
• "Count regions / islands / provinces" → DFS flood fill.
• "Does a path exist" where any path will do → DFS (shortest → BFS!).

Complexity honesty (interviewers test this)

Backtracking is exponential by nature — permutations are O(n!), subsets O(2ⁿ). That's expected; say it plainly and mention pruning (skip invalid branches early) as the optimisation lever.

Recursion shaky? Rebuild the foundation with the recursion guide first.