02.6.2.1 组合子集类
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型
02.6.2.1-001 子集 I(LC 78)怎么枚举?
一句话结论
每个元素选或不选,递归到末尾收集路径;或 for 枚举当前层所选元素并在每个节点收集;无重复元素时无需去重,共 2ⁿ 个子集。
概念解释
- 决策:逐元素二分叉。
- 收集:每个前缀都是子集。
原理流程
- 从下标 0 开始。
- 不选当前 → 递归下一个。
- 选当前 → 加入路径递归后撤销。
代码 / 示例
void dfs(int[] a, int i, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // 每个节点收集
for (int k = i; k < a.length; k++) {
path.add(a[k]);
dfs(a, k + 1, path, res);
path.remove(path.size() - 1);
}
}
常见误区
- 误区:只在末尾收集;正解:子集在各节点收集。
- 误区:忘记把空集加入;正解:初始空路径即一个子集。
追问
- Q:时间复杂度? A:O(n·2ⁿ),2ⁿ 个子集各拷贝 O(n)。
- Q:空间复杂度? A:O(n) 递归栈与路径,输出 O(n·2ⁿ)。
02.6.2.1-002 子集 II 去重(LC 90)怎么做?
一句话结论
先排序,同层相邻同值跳过;不可重复选位置,下一层传 i+1;重复值只在第一个位置展开兄弟分支,避免相同子集重复生成。
概念解释
- 重复来源:相等元素不同位置等价选择。
- 去重:同层只取首个同值。
原理流程
- 排序。
- 循环判
i>start && a[i]==a[i-1]跳过。 - 收集路径后递归 i+1。
代码 / 示例
Arrays.sort(nums);
for (int i = start; i < n; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
res.add(new ArrayList<>(path));
dfs(i + 1);
path.remove(...);
}
常见误区
- 误区:条件写 i>0;正解:层起点 start,写 i>start。
- 误区:不排序就比较相邻;正解:重复值需先相邻。
追问
- Q:子集 II 解的数量? A:去重后为按多重集合生成的子集数。
- Q:空集是否去重? A:空集只有一个,天然唯一。
02.6.2.1-003 组合总和(LC 39,可重复选取)怎么做?
一句话结论
候选无重复、元素可无限次选取;递归从当前下标 i 进入(不传 i+1),和达 target 收集,超 target 剪枝;排序后超限可 break。
概念解释
- 可重复:位置可再次使用。
- 方向:start 固定顺序防重复组合。
原理流程
- 排序候选。
- 从 start 遍历,加入后递归 i。
- 和达标收集,超限剪枝。
代码 / 示例
void dfs(int[] c, int start, int sum, int target, List<Integer> path, List<List<Integer>> res) {
if (sum == target) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i < c.length; i++) {
if (sum + c[i] > target) break;
path.add(c[i]);
dfs(c, i, sum + c[i], target, path, res);
path.remove(path.size() - 1);
}
}
常见误区
- 误区:下一层传 i+1;正解:可重复选要传 i。
- 误区:候选含负数仍 break;正解:负数可回补,只能 continue。
追问
- Q:时间复杂度? A:最坏指数级,随 target 与候选量级。
- Q:为什么不会出现 [2,3] 与 [3,2]? A:start 保证只往后取。
02.6.2.1-004 组合总和 II(LC 40,不可重复 + 去重)怎么做?
一句话结论
候选可含重复值、每个位置最多选一次;排序后同层相邻同值跳过,递归传 i+1;和超 target break 剪枝。
概念解释
- 位置唯一:下标只入路径一次。
- 值去重:同值兄弟等价。
原理流程
- 排序。
- 同层重复跳过。
- 选中递归 i+1,撤销。
代码 / 示例
if (i > start && c[i] == c[i - 1]) continue;
if (sum + c[i] > target) break;
path.add(c[i]);
dfs(i + 1, sum + c[i]);
path.remove(...);
常见误区
- 误区:传 i 导致同位置重复使用;正解:传 i+1。
- 误区:去重条件漏了 start 基准;正解:写 i>start。
追问
- Q:与 LC 39 核心区别? A:可否重复使用同一位置。
- Q:去重后还需要 used 数组吗? A:组合按 start 推进,不需要。
02.6.2.1-005 组合总和 III(LC 216)怎么限定个数与和?
一句话结论
从 1~9 选 k 个数和为 n;回溯记录已选个数与当前和,个数到 k 且和为 n 才收集;个数不足、和超限提前剪枝;不可重复选,下一层 i+1。
概念解释
- 双约束:长度 k、和 n。
- 剪枝:剩余数不足或和超限。
原理流程
- 枚举 1~9。
- 判断个数与和。
- 达标收集,超限终止。
代码 / 示例
if (path.size() == k) {
if (sum == n) res.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= 9; i++) {
if (sum + i > n) break;
path.add(i); dfs(i + 1, sum + i); path.remove(...);
}
常见误区
- 误区:个数到 k 不判和直接收集;正解:必须同时满足和为 n。
- 误区:允许重复选数字;正解:III 要求不同数字。
追问
- Q:剩余个数不足怎么剪? A:
k - size > 9 - i时返回。 - Q:最多选几个? A:k ≤ 9,候选仅 1~9。
02.6.2.1-006 组合总和 IV(LC 377)为什么用 DP 而不是回溯?
一句话结论
IV 求方案数且顺序不同算不同(如 [1,2] 与 [2,1] 都算),是有序硬币凑和;回溯枚举会指数爆炸,DP dp[s]=Σdp[s-x] 计数,外层容量、内层硬币。
概念解释
- 有序:顺序计入方案。
- 计数:不求具体路径。
原理流程
- dp[0]=1。
- 容量外层枚举,硬币内层累加。
- dp[target] 即方案数。
代码 / 示例
int[] dp = new int[target + 1];
dp[0] = 1;
for (int s = 1; s <= target; s++)
for (int x : nums)
if (s >= x) dp[s] += dp[s - x];
常见误区
- 误区:套回溯枚举所有排列;正解:只求计数,DP 更优。
- 误区:外层硬币内层容量;正解:那是无序组合数,IV 要有序排列数。
追问
- Q:与零钱兑换 II 区别? A:II 无序组合数,外层硬币;IV 有序排列数,外层容量。
- Q:复杂度? A:O(n·target),空间 O(target)。
02.6.2.1-007 组合 C(n,k)(LC 77)怎么生成?
一句话结论
从 1~n 选 k 个数;start 控制只往后取,路径长度达 k 收集;不可重复选,递归 i+1;共 C(n,k) 个组合。
概念解释
- 无序组合:顺序固定为升序。
- 长度约束:k。
原理流程
- 从 start 枚举。
- 加入路径递归 i+1。
- size==k 收集。
代码 / 示例
void comb(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i <= n; i++) {
path.add(i);
comb(n, k, i + 1, path, res);
path.remove(...);
}
}
常见误区
- 误区:收集条件写成 size==n;正解:目标长度是 k。
- 误区:传 i 允许重复;正解:组合不重复,传 i+1。
追问
- Q:剪枝条件? A:剩余
n-i+1不足补齐 k 时 break。 - Q:复杂度? A:O(C(n,k)·k)。
02.6.2.1-008 组合问题中元素顺序约定怎么定?
一句话结论
组合不区分顺序,统一按下标递增生成,结果内部元素升序;区分顺序的是排列;写组合回溯时用 start 杜绝回头选,避免同集合重复生成。
概念解释
- 组合:集合,无序。
- 排列:序列,有序。
原理流程
- 判断题名是否区分顺序。
- 组合固定方向选。
- 排列枚举全部未用元素。
代码 / 示例
组合:1≤2 只生成一次;排列:[1,2]、[2,1] 都生成
常见误区
- 误区:把组合当排列枚举;正解:会产生顺序重复解。
- 误区:结果内部顺序不统一;正解:start 保证升序。
追问
- Q:题目说“不同顺序算不同方案”属于哪类? A:排列/有序组合,按排列处理。
- Q:组合结果需要排序输出吗? A:生成时已升序,无需再排。
02.6.2.1-009 电话号码字母组合(LC 17)怎么做?
一句话结论
数字串逐位映射字母表;回溯每层枚举当前数字对应的字母,加入路径递归下一位,长度等于数字串长度时收集;这是“多分支选择序列”型回溯。
概念解释
- 映射:数字 → 字母列表。
- 层级:每位数字一层。
原理流程
- 建数字字母映射。
- 第 i 位枚举对应字母。
- 走完所有数字收集字符串。
代码 / 示例
String[] map = {"", "", "abc", "def", ...};
void dfs(String digits, int i, StringBuilder sb, List<String> res) {
if (i == digits.length()) { res.add(sb.toString()); return; }
for (char c : map[digits.charAt(i) - '0'].toCharArray()) {
sb.append(c);
dfs(digits, i + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
常见误区
- 误区:空数字串返回含空串列表;正解:按题意返回空列表。
- 误区:字母选择后不撤销 StringBuilder;正解:可变容器必须回退。
追问
- Q:复杂度? A:O(3ⁿ 或 4ⁿ) 量级,每数字 3~4 字母。
- Q:映射表怎么存? A:字符串数组按下标索引。
02.6.2.1-010 单词拆分(LC 139)回溯视角怎么看?
一句话结论
回溯枚举每个断点切出的前缀是否在字典中,递归剩余串;直接回溯有重复子串,加记忆化 memo[i] 表示从 i 起能否拆分;本质可转线性 DP。
概念解释
- 状态:剩余起点 i。
- 重复:相同后缀被多次尝试。
原理流程
- 枚举 i 到 j 的子串。
- 字典命中则递归 j+1。
- memo 缓存可行性。
代码 / 示例
Boolean[] memo;
boolean dfs(String s, int i, Set<String> dict) {
if (i == s.length()) return true;
if (memo[i] != null) return memo[i];
for (int j = i + 1; j <= s.length(); j++)
if (dict.contains(s.substring(i, j)) && dfs(s, j, dict))
return memo[i] = true;
return memo[i] = false;
}
常见误区
- 误区:纯回溯不记忆化;正解:后缀重复会指数超时。
- 误区:子串区间切错;正解:前缀
[i,j),递归起点 j。
追问
- Q:DP 状态怎么定义? A:dp[i] 前 i 字符能否拆分。
- Q:复杂度? A:O(n²) 枚举断点,字典查询 O(1) 平均。
02.6.2.1-011 复原 IP 地址(LC 93)怎么切分?
一句话结论
把数字串切成 4 段,回溯记录已切段数与起点;每段 0~255 且无前导零,凑满 4 段且用完所有字符才收集;超限段提前剪枝。
概念解释
- 约束:4 段、每段合法数值。
- 前导零:
0xx非法。
原理流程
- 枚举本段结束位置。
- 校验数值与前导零。
- 递归下一段,4 段收集。
代码 / 示例
void dfs(String s, int start, int seg, List<String> path, List<String> res) {
if (seg == 4) {
if (start == s.length()) res.add(String.join(".", path));
return;
}
for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
String part = s.substring(start, start + len);
if (part.length() > 1 && part.charAt(0) == '0') break;
if (Integer.parseInt(part) > 255) break;
path.add(part);
dfs(s, start + len, seg + 1, path, res);
path.remove(...);
}
}
常见误区
- 误区:分段没用完整串也收集;正解:必须 start 到末尾。
- 误区:前导零只判断单 0;正解:
0合法,01非法。
追问
- Q:每段最长几位? A:3 位,0~255。
- Q:复杂度? A:常数级分段,枚举量很小。
02.6.2.1-012 括号生成(LC 22)怎么回溯?
一句话结论
记录已用左括号数 open、右括号数 close;左括号小于 n 可加 (,右括号小于左括号可加 );长度 2n 收集;用合法性约束剪枝。
概念解释
- 合法前缀:右括号数 ≤ 左括号数。
- 层级:逐字符扩展。
原理流程
- open<n 才放左括号。
- close<open 才放右括号。
- 长度达标收集。
代码 / 示例
void dfs(int n, int open, int close, StringBuilder sb, List<String> res) {
if (sb.length() == 2 * n) { res.add(sb.toString()); return; }
if (open < n) { sb.append('('); dfs(n, open + 1, close, sb, res); sb.deleteCharAt(...); }
if (close < open) { sb.append(')'); dfs(n, open, close + 1, sb, res); sb.deleteCharAt(...); }
}
常见误区
- 误区:右括号只判小于 n;正解:必须 close<open,否则前缀非法。
- 误区:用全排列括号再校验;正解:回溯中按约束生成,天然合法。
追问
- Q:解的数量? A:第 n 个卡特兰数。
- Q:复杂度? A:与合法括号序列数量同阶。
02.6.2.1-013 分割回文串(LC 131)怎么做?
一句话结论
枚举每个断点切出前缀子串,判断是否回文,是则递归剩余部分;收集所有分割方案;回文判断可预处理二维表加速。
概念解释
- 分割:把串切成若干回文段。
- 状态:当前起点。
原理流程
- 枚举终点切前缀。
- 回文则加入路径递归。
- 到末尾收集方案。
代码 / 示例
void dfs(String s, int start, List<String> path, List<List<String>> res) {
if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
for (int j = start + 1; j <= s.length(); j++) {
if (isPalindrome(s, start, j - 1)) {
path.add(s.substring(start, j));
dfs(s, j, path, res);
path.remove(...);
}
}
}
常见误区
- 误区:只判断整串回文;正解:每段前缀都要回文。
- 误区:回文判断遗漏单字符;正解:单字符天然回文。
追问
- Q:怎么加速回文判断? A:预处理
dp[i][j]回文表 O(1) 查。 - Q:复杂度? A:最坏 O(n·2ⁿ) 量级,随分割方案数。
02.6.2.1-014 乘积为目标的子数组组合怎么回溯?
一句话结论
在候选数组上按 start 枚举子集,维护当前乘积,等于目标收集;元素非负时超限可剪枝;注意 1 与 0 对乘积的特殊影响。
概念解释
- 状态:当前乘积、起点。
- 约束:乘积等于目标。
原理流程
- 枚举加入当前元素。
- 更新乘积递归。
- 撤销,超目标剪枝。
代码 / 示例
path.add(a[i]);
dfs(i + 1, prod * a[i]);
path.remove(...);
常见误区
- 误区:0 元素后乘积归零仍继续;正解:0 会使后续乘积保持 0,单独处理。
- 误区:负数乘积回补;正解:带负数不能按超限剪枝。
追问
- Q:与子集和有何异同? A:框架相同,聚合操作由加改乘。
- Q:乘积溢出怎么办? A:按题意用长整型或提前判溢出。
02.6.2.1-015 子集和等于目标的方案怎么计数?
一句话结论
回溯枚举选/不选,记录下标与剩余和;只求个数时可记忆化 (i, 剩余和),等价 01 背包计数;输出具体方案才保留路径枚举。
概念解释
- 计数状态:下标 + 剩余和。
- 转移:选或不选当前元素。
原理流程
- 剩余和为 0 计 1。
- 越界返回 0。
- 选 + 不选累加,memo 缓存。
代码 / 示例
int dfs(int i, int remain) {
if (remain == 0) return 1;
if (i == n || remain < 0) return 0;
return dfs(i + 1, remain) + dfs(i + 1, remain - a[i]);
}
常见误区
- 误区:计数还存路径;正解:只求个数用标量 DP。
- 误区:元素可重复时转移写错;正解:可重复选时选后递归 i 而非 i+1。
追问
- Q:对应哪种背包? A:01 背包计数(不可重复)。
- Q:复杂度? A:O(n·target)。
02.6.2.1-016 组合类“剩余元素不足”剪枝怎么写?
一句话结论
还差 k 个元素时,从当前 start 到末尾的个数必须 ≥ 缺口,否则剪枝;定长组合在循环内也可判断 剩余可选项 < 缺口 提前 break。
概念解释
- 缺口:目标长度 - 已选长度。
- 余量:n - i。
原理流程
- 计算缺口。
- 比较余量。
- 不足则返回/break。
代码 / 示例
if (k - path.size() > n - i) return;
// 循环内:
for (int i = start; n - i >= k - path.size(); i++) { ... }
常见误区
- 误区:余量按整个数组算;正解:只算 start 之后。
- 误区:可重复选取也用该剪枝;正解:可重复时候选不消耗,口径不同。
追问
- Q:剪枝影响正确性吗? A:不影响,不足凑不齐长度。
- Q:定长组合还有哪些剪枝? A:和超限、候选值越界。
02.6.2.1-017 组合中重复值怎么处理?
一句话结论
候选含重复值时先排序,同层相邻同值跳过;位置不可重复选,递归 i+1;输出按值收集,必要时路径存下标区分位置。
概念解释
- 同值不同位置:生成同组合。
- 去重:同层只取第一位置。
原理流程
- 排序。
- 同层判相等跳过。
- 选中后 i+1 递归。
代码 / 示例
if (i > start && a[i] == a[i - 1]) continue;
常见误区
- 误区:重复值也传 i 重用;正解:II 类问题位置唯一。
- 误区:去重条件跨层生效;正解:只在同层兄弟间跳过。
追问
- Q:无重复候选需要这段判断吗? A:不需要。
- Q:去重后组合顺序? A:内部按候选升序。
02.6.2.1-018 子集枚举两种视角怎么对照?
一句话结论
二分叉视角:每个元素选/不选,递归树满二叉;for 枚举视角:每层选一个后续元素,各节点收集子集;两者解集合相同,二分叉写起来短,for 视角便于同层去重与 start 控制。
概念解释
- 二分叉:选/不选两支。
- for 枚举:一层列候选。
原理流程
- 二分叉:不选递归 + 选递归。
- for:循环选当前层元素。
- 对照解集合一致。
代码 / 示例
// 二分叉
dfs(i+1); path.add(a[i]); dfs(i+1); path.remove(...);
// for 枚举
for (k=i; k<n; k++) { path.add(a[k]); dfs(k+1); path.remove(...); }
常见误区
- 误区:二分叉去重容易漏不选分支;正解:重复值两支都要判断。
- 误区:for 视角忘记收集中间节点;正解:子集每层进入即收集。
追问
- Q:哪种更适合组合定长? A:for 枚举,start 推进清晰。
- Q:两种复杂度一样吗? A:分支总量一致。
02.6.2.1-019 组合结果的排序一致性怎么保证?
一句话结论
start 递增选取使每个组合内部元素升序;不同组合之间顺序由枚举顺序自然产生;题目要求结果内部有序即可,组合间顺序通常不作要求;输出前无需再排序。
概念解释
- 内部有序:组合内升序。
- 外部顺序:枚举顺序。
原理流程
- 按下标递增选。
- 路径自然升序。
- 核对题目是否要求整体排序。
代码 / 示例
组合:[1,2,3] 内部升序;结果集顺序随回溯产生
常见误区
- 误区:结果集还要整体排序;正解:多数题目只要求组合内部有序。
- 误区:选值不按下标导致乱序;正解:start 保证下标递增。
追问
- Q:候选无序怎么办? A:先排序候选再回溯,内部即有序。
- Q:去重与排序冲突吗? A:排序是去重前提,不冲突。
02.6.2.1-020 组合子集类复杂度口径怎么报?
一句话结论
子集 O(n·2ⁿ) 时间、O(n) 辅助空间;组合 C(n,k) 量级 O(C(n,k)·k);带和约束按剪枝后实际分支,最坏按满枚举;输出空间为解数 × 单解长度。
概念解释
- 分支量级:2ⁿ 或 C(n,k)。
- 单解代价:路径拷贝 O(k)。
原理流程
- 判断题型是子集还是定长组合。
- 估解的数量级。
- 乘单解拷贝代价,单列输出空间。
代码 / 示例
子集:O(n·2ⁿ);组合:O(C(n,k)·k);辅助 O(n)
常见误区
- 误区:只报递归深度;正解:组合子集分支宽,要看解数量级。
- 误区:把输出空间当辅助空间;正解:res 大小单独说明。
追问
- Q:可重复选取组合复杂度? A:随 target 与候选个数,最坏指数级。
- Q:怎么降低拷贝成本? A:共享前缀或收集时再构造。