07、组合总和II

继续说一下组合总和 2

https://leetcode.cn/problems/combination-sum-ii/

题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5
输出:
[
[1,2,2],
[5]
]

约束条件:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

与前两题的对比

LeetCode 77 (组合):
- 从 [1..n] 中选 k 个数
- 每个数只能用一次
- 无重复元素

LeetCode 39 (组合总和):
- 数组无重复
- 每个数可以用无限次
- start = i (可重复选择)

LeetCode 40 (组合总和 II):
- 数组有重复元素
- 每个数只能用一次
- 需要去重！⭐

如何去重？

问题分析

输入: candidates = [1,1,2], target = 3

如果不去重:
搜索树:
            []
    ┌────┼──┐
    1₁       1₂    2
    │       │    │
   ┌┴┐   ┌┴┐   X
   1₂  2    1₁ 2
   │  │   │  │
   ✗   ✓    ✓  ✗

会产生: [1₁,2], [1₂,2]
实际上这是同一个组合！

关键问题:
在同一层中，相同的数字只能选一次

去重策略

方法: 排序 + 跳过同层重复

步骤:
1. 先排序: [1,1,2]
2. 在同一层遍历时，跳过重复的数字

判断条件:
if (i > start && candidates[i] == candidates[i-1]) {
    continue;  // 跳过同层重复
}

解释:
- i > start: 不是当前层的第一个元素
- candidates[i] == candidates[i-1]: 和前一个相同
- 说明是同层重复，跳过

回溯代码实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();

        // 关键: 必须排序
        sort(candidates.begin(), candidates.end());

        backtrack(candidates, target, 0, 0);
        return result;
    }

private:
    void backtrack(vector<int>& candidates, int target, int sum, int start) {
        // 找到解
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); i++) {
            // 去重: 同一层跳过重复元素
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }

            // 剪枝
            if (sum + candidates[i] > target) {
                break;
            }

            // 回溯三步骤
            path.push_back(candidates[i]);
            backtrack(candidates, target, sum + candidates[i], i + 1);  // i+1: 不重复使用
            path.pop_back();
        }
    }
};

三道题的回溯对比

代码对比

// LeetCode 77 - 组合
void backtrack(int n, int k, int start) {
    if (path.size() == k) {
        result.push_back(path);
        return;
    }

    for (int i = start; i <= n; i++) {
        path.push_back(i);
        backtrack(n, k, i + 1);  // i+1: 不重复
        path.pop_back();
    }
}

// LeetCode 39 - 组合总和
void backtrack(vector<int>& candidates, int target, int sum, int start) {
    if (sum == target) {
        result.push_back(path);
        return;
    }

    for (int i = start; i < candidates.size(); i++) {
        if (sum + candidates[i] > target) {
            break;
        }

        path.push_back(candidates[i]);
        backtrack(candidates, target, sum + candidates[i], i);  // i: 可重复
        path.pop_back();
    }
}

// LeetCode 40 - 组合总和 II ⭐
void backtrack(vector<int>& candidates, int target, int sum, int start) {
    if (sum == target) {
        result.push_back(path);
        return;
    }

    for (int i = start; i < candidates.size(); i++) {
        // 去重: 同层跳过重复
        if (i > start && candidates[i] == candidates[i-1]) {
            continue;  // 新增
        }

        if (sum + candidates[i] > target) break;

        path.push_back(candidates[i]);
        backtrack(candidates, target, sum + candidates[i], i + 1);  // i+1: 不重复
        path.pop_back();
    }
}