08、组合总和III

今天继续来给大家说组合总和 3

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

题目描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字 1 到 9
• 每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。

约束条件:

• 2 <= k <= 9
• 1 <= n <= 60

问题特点

本题 = LeetCode 77 + LeetCode 39 的组合

特点1: 固定个数 k (来自 LeetCode 77)
特点2: 固定总和 n (来自 LeetCode 39)
特点3: 候选数字固定 [1..9]
特点4: 每个数字只能用一次

终止条件: path.size() == k && sum == n

题目很容易理解，通过 1,2,3,4,5,6,7,8,9 这是我们可以使用的集合，然后从集合中，选取一个 K 个元素的无重复元素的子集，相加得 n，看一共有几个这样的子集

回溯思路

剪枝优化

剪枝1: 个数剪枝
if (path.size() > k) return;  // 超过 k 个

剪枝2: 总和剪枝
if (sum > n) return;  // 超过目标和

剪枝3: 提前判断
if (sum + i > n) break;  // 当前数字已超过

剪枝4: 范围剪枝
for (int i = start; i <= 9 - (k - path.size()) + 1; i++)
// 剩余数字不够凑 k 个

代码实现

基础版本

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

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtrack(k, n, 0, 1);
        return result;
    }

private:
    void backtrack(int k, int n, int sum, int start) {
        // 终止条件: 同时满足个数和总和
        if (path.size() == k && sum == n) {
            result.push_back(path);
            return;
        }

        // 剪枝: 个数超了
        if (path.size() > k) {
            return;
        }

        // 剪枝: 总和超了
        if (sum > n) {
            return;
        }

        // 从 start 到 9 选择数字
        for (int i = start; i <= 9; i++) {
            path.push_back(i);
            backtrack(k, n, sum + i, i + 1);  // i+1: 不重复
            path.pop_back();
        }
    }
};

优化版本（更多剪枝）

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

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtrack(k, n, 0, 1);
        return result;
    }

private:
    void backtrack(int k, int n, int sum, int start) {
        // 剪枝: 总和超了
        if (sum > n) {
            return;
        }

        // 终止条件
        if (path.size() == k) {
            if (sum == n) {
                result.push_back(path);
            }
            return;
        }

        // 剪枝: 计算搜索范围
        // 还需要 need = k - path.size() 个数
        // 从 i 到 9 有 9 - i + 1 个数
        // 如果不够就不用搜索了
        int need = k - path.size();
        int end = 9 - need + 1;
        for (int i = start; i <= end; i++) {
            // 剪枝: 当前数字加上已经超过目标
            if (sum + i > n) {
                break;
            }     
            path.push_back(i);
            backtrack(k, n, sum + i, i + 1);
            path.pop_back();
        }
    }
};

剪枝详解

剪枝1: 个数剪枝

// 示例: k=3, 当前 path=[1,2,3,4]
if (path.size() > k) {
    return;  // 已经超过 3 个，不可能找到解
}

// 或者在终止条件中判断
if (path.size() == k) {
    if (sum == n) {
        result.push_back(path);
    }
    return;  // 无论是否满足，都要返回
}

剪枝2: 总和剪枝

// 示例: n=7, 当前 sum=8
if (sum > n) {
    return;  // 已经超过目标，不可能了
}

// 或者在循环中
if (sum + i > n) {
    break;  // 加上当前数字就超了，后面的更大
}

剪枝3: 范围剪枝

// 示例: k=3, 当前 path=[1], start=2
int need = k - path.size();  // need = 3 - 1 = 2
int end = 9 - need + 1;      // end = 9 - 2 + 1 = 8

// 从 2 到 8 选择
// 如果选 9: 后面没有数字了，凑不够 2 个

for (int i = start; i <= end; i++) {
    // ...
}