罗罗编程学习记录
本页内容 展开查看

02.6.2.1 组合子集类

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型

02.6.2.1-001 子集 I(LC 78)怎么枚举?

一句话结论

每个元素选或不选,递归到末尾收集路径;或 for 枚举当前层所选元素并在每个节点收集;无重复元素时无需去重,共 2ⁿ 个子集。

概念解释

  • 决策:逐元素二分叉。
  • 收集:每个前缀都是子集。

原理流程

  1. 从下标 0 开始。
  2. 不选当前 → 递归下一个。
  3. 选当前 → 加入路径递归后撤销。

代码 / 示例

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;重复值只在第一个位置展开兄弟分支,避免相同子集重复生成。

概念解释

  • 重复来源:相等元素不同位置等价选择。
  • 去重:同层只取首个同值。

原理流程

  1. 排序。
  2. 循环判 i>start && a[i]==a[i-1] 跳过。
  3. 收集路径后递归 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 固定顺序防重复组合。

原理流程

  1. 排序候选。
  2. 从 start 遍历,加入后递归 i。
  3. 和达标收集,超限剪枝。

代码 / 示例

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 剪枝。

概念解释

  • 位置唯一:下标只入路径一次。
  • 值去重:同值兄弟等价。

原理流程

  1. 排序。
  2. 同层重复跳过。
  3. 选中递归 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. 枚举 1~9。
  2. 判断个数与和。
  3. 达标收集,超限终止。

代码 / 示例

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] 计数,外层容量、内层硬币。

概念解释

  • 有序:顺序计入方案。
  • 计数:不求具体路径。

原理流程

  1. dp[0]=1。
  2. 容量外层枚举,硬币内层累加。
  3. 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。

原理流程

  1. 从 start 枚举。
  2. 加入路径递归 i+1。
  3. 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. 组合固定方向选。
  3. 排列枚举全部未用元素。

代码 / 示例

组合:1≤2 只生成一次;排列:[1,2]、[2,1] 都生成

常见误区

  • 误区:把组合当排列枚举;正解:会产生顺序重复解。
  • 误区:结果内部顺序不统一;正解:start 保证升序。

追问

  • Q:题目说“不同顺序算不同方案”属于哪类? A:排列/有序组合,按排列处理。
  • Q:组合结果需要排序输出吗? A:生成时已升序,无需再排。

02.6.2.1-009 电话号码字母组合(LC 17)怎么做?

一句话结论

数字串逐位映射字母表;回溯每层枚举当前数字对应的字母,加入路径递归下一位,长度等于数字串长度时收集;这是“多分支选择序列”型回溯。

概念解释

  • 映射:数字 → 字母列表。
  • 层级:每位数字一层。

原理流程

  1. 建数字字母映射。
  2. 第 i 位枚举对应字母。
  3. 走完所有数字收集字符串。

代码 / 示例

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。
  • 重复:相同后缀被多次尝试。

原理流程

  1. 枚举 i 到 j 的子串。
  2. 字典命中则递归 j+1。
  3. 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 非法。

原理流程

  1. 枚举本段结束位置。
  2. 校验数值与前导零。
  3. 递归下一段,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 收集;用合法性约束剪枝。

概念解释

  • 合法前缀:右括号数 ≤ 左括号数。
  • 层级:逐字符扩展。

原理流程

  1. open<n 才放左括号。
  2. close<open 才放右括号。
  3. 长度达标收集。

代码 / 示例

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)怎么做?

一句话结论

枚举每个断点切出前缀子串,判断是否回文,是则递归剩余部分;收集所有分割方案;回文判断可预处理二维表加速。

概念解释

  • 分割:把串切成若干回文段。
  • 状态:当前起点。

原理流程

  1. 枚举终点切前缀。
  2. 回文则加入路径递归。
  3. 到末尾收集方案。

代码 / 示例

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 对乘积的特殊影响。

概念解释

  • 状态:当前乘积、起点。
  • 约束:乘积等于目标。

原理流程

  1. 枚举加入当前元素。
  2. 更新乘积递归。
  3. 撤销,超目标剪枝。

代码 / 示例

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 背包计数;输出具体方案才保留路径枚举。

概念解释

  • 计数状态:下标 + 剩余和。
  • 转移:选或不选当前元素。

原理流程

  1. 剩余和为 0 计 1。
  2. 越界返回 0。
  3. 选 + 不选累加,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。

原理流程

  1. 计算缺口。
  2. 比较余量。
  3. 不足则返回/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;输出按值收集,必要时路径存下标区分位置。

概念解释

  • 同值不同位置:生成同组合。
  • 去重:同层只取第一位置。

原理流程

  1. 排序。
  2. 同层判相等跳过。
  3. 选中后 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 枚举:一层列候选。

原理流程

  1. 二分叉:不选递归 + 选递归。
  2. for:循环选当前层元素。
  3. 对照解集合一致。

代码 / 示例

// 二分叉
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. 核对题目是否要求整体排序。

代码 / 示例

组合:[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)。

原理流程

  1. 判断题型是子集还是定长组合。
  2. 估解的数量级。
  3. 乘单解拷贝代价,单列输出空间。

代码 / 示例

子集:O(n·2ⁿ);组合:O(C(n,k)·k);辅助 O(n)

常见误区

  • 误区:只报递归深度;正解:组合子集分支宽,要看解数量级。
  • 误区:把输出空间当辅助空间;正解:res 大小单独说明。

追问

  • Q:可重复选取组合复杂度? A:随 target 与候选个数,最坏指数级。
  • Q:怎么降低拷贝成本? A:共享前缀或收集时再构造。