Leetcode算法训练日记

Leetcode算法训练日记 | day25

一、组合总和Ⅲ

1.题目

Leetcode：第 216 题

找出所有相加之和为 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
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

2.解题思路

使用回溯算法来解决组合求和问题。backtracking 函数是一个递归函数，它尝试将每个可能的数字添加到当前路径中，并递归地继续添加下一个数字，直到路径长度达到 k 或者当前和超过目标和。每次递归调用时，都会检查当前路径长度是否满足条件以及当前和是否等于目标和，
如果满足，则将其添加到结果中。combinationSum3 函数是公共接口，它初始化结果和路径，然后开始递归过程。

3.实现代码

#include <iostream>
#include <vector>
using namespace std;

// 一、组合总和Ⅲ
class Solution1 {
public:
    vector<vector<int>> result; // 用于存储所有可能组合的结果
    vector<int> path; // 用于存储当前组合的路径

    // 递归函数，用于生成所有可能的组合
    void backtracking(int targetSum, int k, int sum, int starIndex) {
        if (path.size() == k) { // 如果当前路径长度等于 k，表示找到了一个候选组合
            if (sum == targetSum) // 如果当前组合的和等于目标和
                result.push_back(path); // 将当前路径添加到结果中
            return; // 递归返回，不再继续扩展当前路径
        }
        // 遍历从starIndex开始的数字，直到9，因为候选数字集是1到9
        for (int i = starIndex; i <= 9; i++) {
            sum += i; // 将当前数字添加到组合的当前和中
            path.push_back(i); // 将当前数字添加到路径中
            backtracking(targetSum, k, sum, i + 1);// 递归调用backtracking函数，尝试添加下一个数字
            sum -= i; // 回溯
            path.pop_back();// 回溯，移除最后一个数字，尝试其他可能的数字
            
        }
    }

    // 成员函数，用于初始化并开始组合生成过程
    vector<vector<int>> combinationSum3(int n, int k) {
        result.clear(); // 清空之前的组合结果
        path.clear(); // 清空当前路径
        backtracking(n, k, 0, 1); // 调用递归函数，从数字1开始生成组合
        return result; // 返回所有可能的组合结果
    }
};

// 二、组合总和Ⅲ（剪枝优化）
class Solution2 {
public:
    vector<vector<int>> result; // 用于存放所有满足条件的组合结果
    vector<int> path; // 用于记录当前的组合路径

    // 辅助函数，实现回溯算法的递归过程
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        if (sum > targetSum) { // 如果当前和已经超过目标和，直接返回，进行剪枝
            return;
        }
        if (path.size() == k) { // 如果当前组合的长度等于 k
            if (sum == targetSum) { // 如果当前组合的和等于目标和，将其添加到结果集中
                result.push_back(path);
            }
            return; // 如果当前组合的和不等于目标和，直接返回，不进行后续递归
        }
        // 从startIndex开始，尝试所有可能的数字，直到不能再选择更多的数字
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            sum += i; // 将当前数字加入到当前和中
            path.push_back(i); // 将当前数字加入到当前组合路径中
            backtracking(targetSum, k, sum, i + 1); // 递归调用，继续尝试下一个数字
            sum -= i; // 回溯，从当前和中移除最后一个数字
            path.pop_back(); // 回溯，从当前组合路径中移除最后一个数字
        }
    }


    // 成员函数，提供组合求和问题的解法
    vector<vector<int>> combinationSum3(int n, int k) {
        result.clear(); // 清空之前存储的结果集，为新的计算做准备
        path.clear(); // 清空当前的组合路径
        backtracking(n, k, 0, 1); // 调用回溯函数，从数字1开始尝试组合
        return result; // 返回所有满足条件的组合结果
    }
};


//测试
int main()
{
    Solution1 s;
    vector<vector<int>> result;
    int n, k;
    cout << "n = ";
    cin >> n;
    cout << "k = ";
    cin >> k;
    result =s.combinationSum3(n, k);
    cout << "所有的组合有：" << endl;
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < k; j++) {
            cout << result[i][j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}