Given a grid of characters and a word, return true if the word can be formed by a path of horizontally/vertically adjacent cells, each cell used at most once. e.g. find 'ABCCED' in the letter grid.
Grid backtracking: DFS that marks a cell used, explores neighbours, and — crucially — un-marks on the way out so other paths can reuse it.
This is DFS with backtracking on a grid, and it differs from flood-fill (Number of Islands) in one essential way: because a cell may be reused by a DIFFERENT path, you must undo your mark when a branch fails. Start a DFS from every cell matching word[0]. At depth k, if the current cell equals word[k], temporarily mark it (e.g. overwrite with a sentinel like '#'), recurse into the four neighbours for word[k+1], and if none succeed, restore the original character before returning false. That restore is the backtracking step — skip it and you wrongly forbid cells on sibling paths. Success is reaching k === word.length - 1. Recognition signal: 'find a path/arrangement subject to a used-once constraint' → DFS that mutates state going in and reverts it coming out. Worst case O(cells · 4^len) since each step branches four ways.
Search for a path or arrangement on a grid/board where cells (or choices) can't repeat within one attempt → DFS that marks state on entry and reverts it on exit.
Time O(m·n·4^L) · Space O(L) recursion (L = word length)