摘要：用来存放每一个可能的结果最终结果深度优先遍历剪枝当遍历到底个数是，如果的元素个数剩余元素个数时，就不满足条件了中元素个数达到，表示深度优先遍历到达最深处了。
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路：
如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；
回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
为什么说是在一棵树上的深度优先遍历呢？比如说，你现在要解决一个问题，这个问题被分为了若干的步骤，对于每一个步骤都有多个方法到下一个步骤。（听君一席话，就是一席话，嘿嘿嘿！！）。就是说我们么一个步骤的选择都是可以返回来更换的。
就拿本题来说：
比如说给了4和3这两个数据；我们要从1,2,3,4,这4个数里面取3个数。很容易分析出来：当我们第一个数取1的时候，第二个数可以去2,3,4,.........。一次推下去。我们会得到一棵一棵的树。样子就是这个样子（这个不是我画的，我去LeetCode的题解上找到哈哈哈哈！！）
想明白这个过程，那我们的解题办法就来了。对于[1 n]里面的每一个数，在最后选择的k个数里面的只有两种状态，要么它在，要么它不在。所以我们只需要去遍历这n个数，然后用一个数组temp把放入最后结果的数记录下来。由于我们是从小到大遍历，所以当我们把当前元素在最后结果里面的记录完以后，后面再记录的结果就不会再包含当前元素了。
class Solution {public: //temp 用来存放每一个可能的结果 vector temp; //最终结果 vector> ans; //深度优先遍历 void dfs(int cur, int n, int k) { // 剪枝：当遍历到底cur个数是，如果temp的元素个数s+剩余元素个数t> combine(int n, int k) { dfs(1, n, k); return ans; }}; 思路：通过上一题，这一题理解起来就更方便了。全部排列顺序，就是上面的那个图，第二次先选择了2以后还可以继续选择1；所以我们只需要把每次选取的元素交换到数组左边，这样就可以和上一题的流程一样了，不过记住记住排列的时候，未选择的元素都可以来占当前cur的位置，由于我们将未选择的元素都交换到cur的右边，所以从cur遍历一遍就可以了。就是这么简单，k默认为n就可以了。
class Solution {public: void dfs(vector>& res, vector& output, int cur, int len){ // 所有数都填完了 if (cur == len) { res.emplace_back(output); return; } //这里每一个数组右边的数都可以当做第cur个元素 for (int i = cur; i < len; ++i) { // 动态维护数组，将未选取的元素交换到数组右边 swap(output[i], output[cur]); // 继续递归填下一个数 dfs(res, output, cur + 1, len); // 撤销交换操作 swap(output[i], output[cur]); } } vector> permute(vector& nums) { vector > res; dfs(res, nums, 0, (int)nums.size()); return res; }}; 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
思路： 注意理解题目要求，题目是说每个子母可以进行大小写变换，但是没有说可以改变位置哦。
class Solution {public: void dfs(vector &res,int cur,string &s,int len){ //数字不变 while(cur= "0" && s[cur] <= "9") cur++; if(cur == len){ res.emplace_back(s); return ; } //子母转变大小写 if(s[cur]>="a"&&s[cur]<="z") s[cur] = toupper(s[cur]); else s[cur] = tolower(s[cur]); dfs(res,cur+1,s,len); //子母不转变大小写 if(s[cur]>="a"&&s[cur]<="z") s[cur] = toupper(s[cur]); else s[cur] = tolower(s[cur]); dfs(res,cur+1,s,len); } vector letterCasePermutation(string s) { vector res; int len = s.length(); dfs(res,0,s,len); return res; }}; 芜湖~~~~~~~~~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123336.html
摘要：斩从第题开始，到现在也差不多快一年了，回顾纪念一下。当时对回溯动态规划也都只是上课的时候学过，也并不熟练。最经典的例子就是斐波那契数列了，求第项数列的值。 leetcode 100 斩！从第 1 题开始，到现在也差不多快一年了，回顾纪念一下。 showImg(https://segmentfault.com/img/bVbu461?w=661&h=191); 为什么开始刷题？ 从大一就...
摘要：现在发出来的版本，我重新使用了语言实现。其实我之前介绍的老师课程也大量参考和使用算法这本书上的思路和例题。看这本书主要是让我觉得算法可以以比较轻松的方式入门。剑指这本书主要用于准备算法面试，在网络上备受好评。 我是一个半路出家的程序员，在我刚开始从事编码工作的头几年，我没有接触过算法和数据结构，觉得它们是只会在我找工作的时候用得到的知识。尽管有很多人跟我说过算法和数据结构无比重要，我也...
马上就要开始啦这次共组织15个组队学习 涵盖了AI领域从理论知识到动手实践的内容 按照下面给出的最完备学习路线分类 难度系数分为低、中、高三档 可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
阅读 2543·2021-11-18 10:02
阅读 2572·2021-11-15 11:38
阅读 3646·2021-11-12 10:36
阅读 653·2021-11-12 10:34
阅读 2854·2021-10-21 09:38
阅读 1396·2021-09-29 09:48
阅读 1427·2021-09-29 09:34
阅读 1042·2021-09-22 10:02
