淄博网站建设铭盛信息,丹阳信息网,最好的网站模板下载网站,广西建设网官网在线服务本文主要讲解组合的要点与细节#xff0c;以及回溯算法的解题步骤#xff0c;按照步骤思考更方便理解
c和java代码如下#xff0c;末尾 给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点#xff1a; …本文主要讲解组合的要点与细节以及回溯算法的解题步骤按照步骤思考更方便理解
c和java代码如下末尾 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点
1. 首先这道题的暴力解法是k层for循环遍历所有的情况。但是这样子时间复杂度会很高。所以对于这类排列组合的问题通常我们使用回溯算法来进行遍历可以花一分钟参考回溯的前言概述。 2. 然后让我们来回顾一下回溯回溯本质是一个树结构通常是由两个结构组成for递归。 其中for用来表示树的宽度遍历每层的集合元素集可以理解一个节点有多少个孩子这个for循环就执行多少次。 递归用来表示树的深度 3. 对于本题要求我们需要先创建两个数组一个用来存放最终的结果一个用来存放过程中每次的结果
vectorvectorint res; //用来存放最终的结果
vectorint temp; //用来存放过程中每次的结果4. 接着我们就可以考虑回溯算法的实现具体包括两部分for循环递归
首先我们来考虑递归说到递归就要思考递归三要素
递归函数参数与返回值终止条件单层递归逻辑
返回值由于我们是直接操作数组不像二叉树一样需要返回节点所以递归的返回值是void
参数回溯算法中的递归参数较多我们在写代码过程中慢慢添加
终止条件也就是我们收集结果的条件当我们的temp存放的数量等于k时就需要收集结果了
单层递归逻辑添加当前元素a到temp中——a向下递归——移除刚才添加的元素a 其次让我们考虑一下for循环的细节 for循环的起始值应该是什么呢 这个细节是回溯中重要的点因为本题是“组合”所以不需要顺序即{12}和{21}是一个意思只保留一个所以下一层递归时起始值就1从而达到去重的目的。 void backtracing(int n, int k,vectorvectorint res, vectorint temp,int start) {//终止条件if (temp.size() k) {//收集结果res.push_back(temp);return;}for (int i start; i n; i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i 1);//相下递归起始值1temp.pop_back();//删除刚才添加的元素实现回溯}return;} 以上就是回溯的整体逻辑让我们总结一下重要的细节
递归的返回值递归的终止条件for循环的起始值
在回溯过程中大家重点思考一下这几个细节点有助于我们更好的实现代码
如果觉得我的讲解有一点帮助十分感谢您的喜欢。
c代码
#includebits/stdc.h
using namespace std;class Solution {
public:vectorvectorint combine(int n, int k) {//组合不考虑顺序vectorvectorint res;vectorint temp;backtracing(n, k, res, temp, 1);return res;}void backtracing(int n, int k,vectorvectorint res, vectorint temp,int start) {//终止条件if (temp.size() k) {//收集结果res.push_back(temp);return;}for (int i start; i n; i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i 1);//相下递归temp.pop_back();//删除刚才添加的元素实现回溯}return;}};
java代码 class Solution {public ListListInteger combine(int n, int k) {ListListInteger res new ArrayListListInteger();ListInteger temp new ArrayList();backtracking(n, k, res, temp, 1);return res;}public void backtracking(int n, int k, ListListInteger res, ListInteger temp, int start) {//终止条件if (temp.size() k) {res.add(new ArrayList(temp));return;}for (int i start; i n; i) {temp.add(i);backtracking(n, k, res, temp, i 1);temp.remove(temp.size() - 1);}return;}
}
