西安学校部门定制网站建设公司,上海网页制作培训班,齐家网装修,想给公司做个网站一、组合问题
1.题目
Leetcode#xff1a;第 77 题
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 示例 1#xff1a;
输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4…一、组合问题
1.题目
Leetcode第 77 题
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]
2.解题思路
使用回溯算法来解决组合问题。backtracking 函数是一个递归函数它尝试将每个可能的元素添加到当前路径中并递归地继续添加下一个元素直到路径长度达到 k。每次递归调用时都会检查当前路径长度是否满足条件如果满足则将其添加到结果中。combine 函数是公共接口它初始化结果和路径然后开始递归过程。
3.实现代码
#include iostream
#include vector
using namespace std;// 一、组合问题
class Solution {
public:vectorvectorint result; // 用于存储所有可能组合的结果vectorint path; // 用于存储当前组合// 递归函数用于生成所有可能的组合void backtracking(int n, int k, int starIndex) {if (path.size() k) { // 如果当前路径长度等于 k表示找到了一个有效的组合result.push_back(path); // 将当前路径添加到结果中return; // 递归返回不再继续扩展当前路径}for (int i starIndex; i n; i) { // 从当前起始索引开始遍历所有可能的元素path.push_back(i); // 将当前元素添加到路径中backtracking(n, k, i 1); // 递归调用 backtracking 函数尝试添加下一个元素path.pop_back(); // 回溯移除最后一个元素尝试其他可能的元素}}// 主函数用于初始化并开始组合生成过程vectorvectorint combine(int n, int k) {result.clear(); // 清空之前的组合结果path.clear(); // 清空当前组合backtracking(n, k, 1); // 调用递归函数从索引 1 开始生成组合return result; // 返回所有可能的组合结果}
};// 二、组合问题剪枝优化
class Solution {
public:vectorvectorint result; // 用于存储所有可能组合的结果vectorint path; // 用于存储当前组合// 递归函数用于生成所有可能的组合void backtracking(int n, int k, int starIndex) {if (path.size() k) { // 如果当前路径长度等于 k表示找到了一个有效的组合result.push_back(path); // 将当前路径添加到结果中return; // 递归返回不再继续扩展当前路径}// 从当前起始索引开始遍历所有可能的元素for (int i starIndex; i n-(k-path.size())1; i) {//剪枝优化path.push_back(i); // 将当前元素添加到路径中backtracking(n, k, i 1); // 递归调用 backtracking 函数尝试添加下一个元素path.pop_back(); // 回溯移除最后一个元素尝试其他可能的元素}}// 主函数用于初始化并开始组合生成过程vectorvectorint combine(int n, int k) {result.clear(); // 清空之前的组合结果path.clear(); // 清空当前组合backtracking(n, k, 1); // 调用递归函数从索引 1 开始生成组合return result; // 返回所有可能的组合结果}
};//测试
int main()
{Solution s;vectorvectorint result;int n,k;cout n ;cin n;cout k ;cin k;results.combine(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以上皆是本人在探索算法旅途中的浅薄见解诚挚地希望得到各位的宝贵意见与悉心指导若有不足或谬误之处还请多多指教。
