本地丹阳网站建设,家在深圳业主论坛,wordpress国内能用吗,重庆建设工程信息网(管理平台)回溯算法终于开始了#xff01;
题目链接#xff1a;leetcode 77. 组合
文章讲解#xff1a;代码随想录 77. 组合讲解
视频讲解#xff1a;带你学透回溯算法-组合问题#xff08;对应力扣题目#xff1a;77.组合#xff09;
思路和解法
题目#xff1a; 给定两个整…回溯算法终于开始了
题目链接leetcode 77. 组合
文章讲解代码随想录 77. 组合讲解
视频讲解带你学透回溯算法-组合问题对应力扣题目77.组合
思路和解法
题目 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 想法 这道题的思路和想象中的回溯有点区别我以为回溯是可以不需要额外的太多考虑而只考虑递归即可。但事实上需要自己先做好一些细节处理工作比如这道题递归函数的构思是需要计划好的因为本身并不存在一个树结构因此在思考解题过程中需要自己给出一个树的结构比如选了1剩下的就要从234里选这样。所以我想应该是再考虑用回溯算法解题时无论如何要先尝试用树结构画出一幅图像然后再思考递归函数的逻辑。另外感觉这个递归函数的设计还是非常灵活的自己如果有想法还是要自信一点尝试多写写。剪枝优化这个也需要思维敏捷才行多练习吧。
class Solution {
public://排列组合是暴力求解的问题在求解过程中会画出树形结构因此考虑到用回溯算法解决//递归函数参数和返回值void 参数n, k其他想到再加 需要指定起始数字//需要存储一条结果vectorint path;vectorvectorint result;void backTracking(int n, int k, int startIndex) {//终止条件if (path.size() k) {//存入结果result.push_back(path);//自己忘记写return了return ;}//递归处理过程 从startIndex开始每个都放入path一次然后向下递归//然后考虑剪枝优化 一共需要k个数字当前有path.size()个还需要k-path,size()个根据i的情况来看还剩n-i1个所以需要k-path.size()n-i1ipath.size()-kn1或者n-(k-path.size())1// for (int i startIndex; i n; i) {// path.push_back(i);// backTracking(n, k, i 1);// path.pop_back();// }for (int i startIndex; i n - (k - path.size() ) 1; i) {path.push_back(i);backTracking(n, k, i 1);path.pop_back();}return ;}vectorvectorint combine(int n, int k) {path.clear();result.clear();backTracking(n, k, 1);return result;}
};
