一、组合总和Ⅲ
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
#include using namespace std; // 一、组合总和Ⅲ class Solution1 { public: vector > result; // 用于存储所有可能组合的结果 vector 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 > combinationSum3(int n, int k) { result.clear(); // 清空之前的组合结果 path.clear(); // 清空当前路径 backtracking(n, k, 0, 1); // 调用递归函数,从数字1开始生成组合 return result; // 返回所有可能的组合结果 } }; // 二、组合总和Ⅲ(剪枝优化) class Solution2 { public: vector > result; // 用于存放所有满足条件的组合结果 vector 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 > combinationSum3(int n, int k) { result.clear(); // 清空之前存储的结果集,为新的计算做准备 path.clear(); // 清空当前的组合路径 backtracking(n, k, 0, 1); // 调用回溯函数,从数字1开始尝试组合 return result; // 返回所有满足条件的组合结果 } }; //测试 int main() { Solution1 s; vector > 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; } ps:以上皆是本人在探索算法旅途中的浅薄见解,诚挚地希望得到各位的宝贵意见与悉心指导,若有不足或谬误之处,还请多多指教。