5 篇
回溯题目专区
回溯有个增量构造答案的过程，这个过程通常用递归实现。
回溯三问
题目描述 给定一个只包含数字 2-9 的字符串 digits，要求返回它能够表示的所有字母组合。数字和字母的对应关系与电话九宫格按键一致，其中 1 不对应任何字母。 如果输入为空字符串，就没有可以组合的内容，直接返回空数组。 思路 这题是很典型的回溯题：每个数字对应一组候选字母，我们要从每一组里选一个字母，按顺序拼成长
题目描述 给定一个整数 n，表示需要生成 n 对括号。要求返回所有可能的、并且有效的括号组合。 有效括号组合需要满足：任意位置之前的右括号数量不能超过左括号数量，并且最终左右括号数量都等于 n。 括号一多就容易盯着屏幕发愣，所以先抓住“前缀合法”这张照片～ 思路 这题可以把生成过程看成一棵回溯搜索树：每一
题目描述 给定一个不含重复数字的数组 nums，要求返回它的所有可能全排列。答案可以按任意顺序返回。 全排列要求每个数字都使用一次，并且不同顺序算作不同结果。 思路 这题可以把排列看成“给每个位置选一个数”。path[i] 表示排列中第 i 个位置放什么数字，所以回溯函数 dfs(i) 就是在决定第 i 个位置要填 n
题目描述 给定两个整数 n 和 k，要求从范围 [1, n] 中选出所有可能的 k 个数的组合。答案可以按任意顺序返回。 组合只关心选了哪些数，不关心选择顺序，所以 [1, 2] 和 [2, 1] 属于同一种组合。 思路 这题也是标准回溯题，不过重点不是“能不能选”，而是“怎样避免重复组合”。嘿嘿，如果把每个数字都当成
题目描述 给定一个 m x n 的二维字符网格 board 和一个字符串 word，判断 word 是否存在于网格中。 单词需要按顺序由相邻单元格中的字符组成，相邻只包含水平和垂直方向。同一个单元格在同一次搜索路径中不能被重复使用。 思路 这题可以把每个格子都当作单词的起点，然后从这个起点开始做深度优先搜索。递归函数
