Word Search

Implement Trie

Combination Sum

Find a word by backtracking through adjacent grid cells.

Return whether `word` can be formed from horizontally or vertically adjacent board cells without reusing a cell.

## Example
```json
Input: {"board":["ABCE","SFCS","ADEE"],"word":"ABCCED"}
Output: true
```

## Constraints
- 1 <= rows, columns <= 6
- 1 <= word.length <= 15
- Board and word contain letters

## Follow-up
Which frequency or prefix checks can reject impossible searches early?

The key pattern is: DFS backtracks over matching adjacent cells. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.