做彩票网站是违法的吗,怎么做网站自动响应,天津免费网站建站模板,深圳定制建站网站建设一、组合总和Ⅲ
1.题目
Leetcode#xff1a;第 216 题 找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺…一、组合总和Ⅲ
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个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。
2.解题思路
使用回溯算法来解决组合求和问题。backtracking 函数是一个递归函数它尝试将每个可能的数字添加到当前路径中并递归地继续添加下一个数字直到路径长度达到 k 或者当前和超过目标和。每次递归调用时都会检查当前路径长度是否满足条件以及当前和是否等于目标和 如果满足则将其添加到结果中。combinationSum3 函数是公共接口它初始化结果和路径然后开始递归过程。
3.实现代码
#include iostream
#include vector
using namespace std;// 一、组合总和Ⅲ
class Solution1 {
public:vectorvectorint result; // 用于存储所有可能组合的结果vectorint 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到9for (int i starIndex; i 9; i) {sum i; // 将当前数字添加到组合的当前和中path.push_back(i); // 将当前数字添加到路径中backtracking(targetSum, k, sum, i 1);// 递归调用backtracking函数尝试添加下一个数字sum - i; // 回溯path.pop_back();// 回溯移除最后一个数字尝试其他可能的数字}}// 成员函数用于初始化并开始组合生成过程vectorvectorint combinationSum3(int n, int k) {result.clear(); // 清空之前的组合结果path.clear(); // 清空当前路径backtracking(n, k, 0, 1); // 调用递归函数从数字1开始生成组合return result; // 返回所有可能的组合结果}
};// 二、组合总和Ⅲ剪枝优化
class Solution2 {
public:vectorvectorint result; // 用于存放所有满足条件的组合结果vectorint path; // 用于记录当前的组合路径// 辅助函数实现回溯算法的递归过程void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum targetSum) { // 如果当前和已经超过目标和直接返回进行剪枝return;}if (path.size() k) { // 如果当前组合的长度等于 kif (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(); // 回溯从当前组合路径中移除最后一个数字}}// 成员函数提供组合求和问题的解法vectorvectorint combinationSum3(int n, int k) {result.clear(); // 清空之前存储的结果集为新的计算做准备path.clear(); // 清空当前的组合路径backtracking(n, k, 0, 1); // 调用回溯函数从数字1开始尝试组合return result; // 返回所有满足条件的组合结果}
};//测试
int main()
{Solution1 s;vectorvectorint 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以上皆是本人在探索算法旅途中的浅薄见解诚挚地希望得到各位的宝贵意见与悉心指导若有不足或谬误之处还请多多指教。
