0040. Combination Sum II¶
题目信息¶
- 题号:
组合总和 II
- 难度:
Medium
- 主题:
数组、回溯、排序、同层去重
- 原题:
- 重点:
从枚举下标子集后去重,推导到排序后跳过同层等值分支,并保证每个位置最多使用一次
题目重述¶
给定正整数数组 candidates 和正整数 target,找出所有元素之和恰好等于 target 的不同组合。
数组中可以出现相同数值,但每个数组位置在一个组合中最多使用一次。组合只按数值及其出现次数区分,内部顺序不同 不算新组合,因此相同数值组合只能返回一次。答案顺序不限。
candidates 的长度位于 [1, 100],每个元素位于 [1, 50],target 位于 [1, 30]。
自建示例¶
candidates = [1, 1, 1, 2]、target = 3,返回[[1, 1, 1], [1, 2]];三个1来自 三个不同位置,因此可以同时使用;candidates = [2, 5, 2, 1, 2]、target = 5,返回[[1, 2, 2], [5]];三个位置上的2不应制造多份[1, 2, 2];candidates = [3, 4, 7]、target = 2,返回[];排序后首个候选已经超过剩余目标;candidates = [1, 2, 3]、target = 3,返回[[1, 2], [3]];同一位置不能在组合中重复使用。
C++ 实现¶
#include <algorithm>
#include <set>
#include <utility>
#include <vector>
class Solution {
private:
void subsetDfs(
const std::vector<int>& candidates,
int index,
int remaining,
std::vector<int>& path,
std::set<std::vector<int>>& unique
) {
if (remaining == 0) {
std::vector<int> canonical = path;
std::sort(canonical.begin(), canonical.end());
unique.insert(canonical);
return;
}
if (index == static_cast<int>(candidates.size()) || remaining < 0) {
return;
}
subsetDfs(candidates, index + 1, remaining, path, unique);
path.push_back(candidates[index]);
subsetDfs(
candidates,
index + 1,
remaining - candidates[index],
path,
unique
);
path.pop_back();
}
std::vector<std::vector<int>> enumerateSubsetsThenDeduplicate(
const std::vector<int>& candidates,
int target
) {
std::set<std::vector<int>> unique;
std::vector<int> path;
subsetDfs(candidates, 0, target, path, unique);
return {unique.begin(), unique.end()};
}
std::vector<std::pair<int, int>> buildFrequencyGroups(
std::vector<int> candidates
) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::pair<int, int>> groups;
for (int value : candidates) {
if (groups.empty() || groups.back().first != value) {
groups.push_back({value, 1});
} else {
++groups.back().second;
}
}
return groups;
}
void frequencyDfs(
const std::vector<std::pair<int, int>>& groups,
int group,
int remaining,
std::vector<int>& path,
std::vector<std::vector<int>>& result
) {
if (remaining == 0) {
result.push_back(path);
return;
}
if (group == static_cast<int>(groups.size())) {
return;
}
const auto [value, frequency] = groups[group];
const int maximum = std::min(frequency, remaining / value);
for (int used = 0; used <= maximum; ++used) {
for (int count = 0; count < used; ++count) {
path.push_back(value);
}
frequencyDfs(
groups,
group + 1,
remaining - used * value,
path,
result
);
for (int count = 0; count < used; ++count) {
path.pop_back();
}
}
}
std::vector<std::vector<int>> searchByFrequencyGroups(
std::vector<int> candidates,
int target
) {
const auto groups = buildFrequencyGroups(std::move(candidates));
std::vector<std::vector<int>> result;
std::vector<int> path;
frequencyDfs(groups, 0, target, path, result);
return result;
}
void sameLevelDfs(
const std::vector<int>& candidates,
int start,
int remaining,
std::vector<int>& path,
std::vector<std::vector<int>>& result
) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int index = start;
index < static_cast<int>(candidates.size());
++index) {
if (index > start && candidates[index] == candidates[index - 1]) {
continue;
}
const int value = candidates[index];
if (value > remaining) {
break;
}
path.push_back(value);
sameLevelDfs(candidates, index + 1, remaining - value, path, result);
path.pop_back();
}
}
std::vector<std::vector<int>> sortedSameLevelDeduplication(
std::vector<int> candidates,
int target
) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int>> result;
std::vector<int> path;
sameLevelDfs(candidates, 0, target, path, result);
return result;
}
public:
std::vector<std::vector<int>> combinationSum2(
std::vector<int>& candidates,
int target
) {
return sortedSameLevelDeduplication(candidates, target);
}
};
题解¶
下标子集基线¶
每个数组位置只有选与不选两种决定。subsetDfs 处理完下标 index 后递归到 index + 1,因此任何路径都
不会重复使用同一位置;所有下标子集都会被枚举,所以不会遗漏合法组合。
下标不同却可能表示相同的数值组合。若输入含 1a、1b 和 2,选择 {1a, 2} 与 {1b, 2}
是两个下标子集,却都对应 [1, 2]。基线方法只能在命中目标后排序路径,再交给集合删除重复结果。
事后去重保证答案正确,却没有减少搜索:等价下标分支仍被完整展开。优化目标是让相同数值组合只进入搜索树一次。
频次分组模型¶
排序后可以把相同值压缩为 (value, frequency)。例如 [1, 1, 1, 2] 变为:
(1, 3), (2, 1)
处理一组数值时,只需决定使用 0..frequency 次,并受 remaining / value 限制。每个组合对应唯一的次数向量,
例如 [1, 1, 1] 对应 (3, 0),[1, 2] 对应 (1, 1),重复下标身份因此消失。
searchByFrequencyGroups 从状态模型中解决了去重,但每次枚举使用次数都要批量追加和撤销元素。还可以保留下标回溯
模板,只在等价分支出现时直接跳过。
排序后的搜索空间¶
主方法先排序数组,再让 start 表示本层允许选择的最小下标。路径中的下标严格递增,因此路径数值也保持非递减,
同一个组合不会再因元素顺序不同而出现多次。
选择 candidates[index] 后递归到 index + 1,表示当前位置已经消耗。后面即使还有相同数值,也属于不同位置,
可以在更深层继续选择。这正是本题与可无限复用候选的 0039 的核心差异。
同层等值分支¶
固定相同的 path、start 和 remaining 时,若本层先选择两个相邻等值位置中的前一个或后一个,形成的数值
前缀完全相同。后一个位置可使用的后缀还更短,不可能产生前一个分支无法产生的新数值组合,因此跳过:
if (index > start && candidates[index] == candidates[index - 1]) {
continue;
}
index > start 把去重限制在同一递归层。进入下一层后,后一个等值位置可能是该层第一个候选,必须允许选择,否则
会错误删除 [1, 1]、[1, 1, 1] 等合法组合。
以 [1a, 1b, 1c, 2]、目标 3 为例:根层只从 1a 开始等值分支;第二层仍可选 1b,第三层仍可
选 1c,得到 [1, 1, 1];第二层也可跳到 2,得到 [1, 2]。
任意合法组合按非递减顺序表示后,都可以依次选择每层最早可用的对应下标,因此不会遗漏。若两条路径生成相同组合, 它们第一次选择不同下标时必然处于同层且数值相同,较后的分支会被上述条件跳过,因此组合也不会重复。
剩余目标剪枝¶
所有候选均为正数。排序后若当前 value > remaining,后续值只会更大,本层不可能再命中目标,可以直接
break。选择一个候选后,remaining 严格减小;当它变为零时,当前路径恰好构成答案。
每轮递归开始时保持三个状态:路径使用的下标严格递增,路径数值非递减,remaining 等于目标减去路径和。
同层去重只删除等价首选,index + 1 保证位置不复用,正数剪枝只排除必然超出剩余目标的后缀。
状态演化¶
对排序后的 [1, 2, 2, 2, 5]、目标 5:
路径 |
|
本层动作 |
结果 |
|---|---|---|---|
|
0 |
选择 |
剩余 |
|
1 |
选择第一个 |
剩余 |
|
2 |
选择下一个 |
得到 |
|
1 |
跳过本层其余等值 |
不生成重复组合 |
|
0 |
选择 |
得到 |
代码演进¶
enumerateSubsetsThenDeduplicate 严格执行每个位置只使用一次,但先搜索全部等价分支,再用集合去重。
searchByFrequencyGroups 把相同值压缩为使用次数,从状态定义中删除重复下标身份。
sortedSameLevelDeduplication 保留下标回溯结构,通过排序、同层跳过和 index + 1 同时实现结果去重与位置单次
使用,并利用正数有序性提前结束无效后缀。公开入口采用该方法。
复杂度分析¶
设输入长度为 n。排序需要 O(n log n)。下标子集方法最多访问 2^n 个选择状态,规范化答案还需要路径
排序与集合插入。
频次分组若各数值出现次数为 f_1, f_2, ...,忽略和值剪枝时最多枚举
(f_1 + 1)(f_2 + 1)... 个次数状态。主方法的搜索树最坏仍可达到 O(2^n),但同层去重与正数剪枝会删除
大量状态。除输出外,递归栈与路径最多保存 n 个元素,额外空间为 O(n)。