> For the complete documentation index, see [llms.txt](https://liuzhenglaichn.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuzhenglaichn.gitbook.io/algorithm/graph/depth-first-search.md).

# Depth First Search

Note that if a graph is acyclic, we don't need to keep a set of visited nodes to prevent going into a loop.

Example: [797. All Paths From Source to Target (Medium)](https://leetcode.com/problems/all-paths-from-source-to-target/)

## Problems

* [17. Letter Combinations of a Phone Number (Medium)](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
* [39. Combination Sum (Medium)](https://leetcode.com/problems/combination-sum/)
* [40. Combination Sum II (Medium)](https://leetcode.com/problems/combination-sum-ii/)
* [77. Combinations (Medium)](https://leetcode.com/problems/combinations/)
* [212. Word Search II (Hard)](https://leetcode.com/problems/word-search-ii/)
* [216. Combination Sum III (Medium)](https://leetcode.com/problems/combination-sum-iii/)
* [797. All Paths From Source to Target (Medium)](https://leetcode.com/problems/all-paths-from-source-to-target/)
* [1219. Path with Maximum Gold (Medium)](https://leetcode.com/problems/path-with-maximum-gold/)
* [1601. Maximum Number of Achievable Transfer Requests (Hard)](https://leetcode.com/problems/maximum-number-of-achievable-transfer-requests/)