【递归、搜索与回溯算法】综合练习（二）

📝前言说明：

• 本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

点击链接	开始学习
导论	递归 (一) 、递归 (二)
二叉树的深搜	穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝
综合练习（一）	综合练习（二）
综合练习（三）	综合练习（四）
FloodFill算法	记忆化搜索

---

77. 组合

题目链接：https://leetcode.cn/problems/combinations/description/

个人解

思路：

• 简单题，不如之前的难

屎山代码：

class Solution {
public:vector<vector<int>> ans;vector<int> path;void dfs(int n, int k, int pos){if(path.size() == k){ans.emplace_back(path);return;}for(int i = pos; i <= n; i++){path.push_back(i);dfs(n, k, i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {dfs(n, k, 1);return ans;}
};

时间复杂度：O(C(n, k))
空间复杂度：O(C(n, k) * k)

---

494. 目标和

题目链接：https://leetcode.cn/problems/target-sum/description/

个人解

屎山代码：

class Solution {
public:int ans = 0;void dfs(vector<int>& nums, int target, int pos, int current){if(pos == nums.size()){if(current == target) ans += 1;return;}dfs(nums, target, pos + 1, current + nums[pos]);dfs(nums, target, pos + 1, current - nums[pos]);}int findTargetSumWays(vector<int>& nums, int target) {dfs(nums, target, 0, 0);return ans;}
};

---

39. 组合总和

题目链接：https://leetcode.cn/problems/combination-sum/description/

个人解

思路：

• 因为可以重复选择，所以，每一层，我们可以选择选当前的数 / 去选下一个数
• 因为每一次选了下一个数以后就不能再回头选原来的数了，所以不会出现重复组的情况

用时：
屎山代码：

class Solution {
public:vector<vector<int>> ans;vector<int> path;void dfs(vector<int>& candidates, int target, int current, int pos){if(current == target){ans.emplace_back(path);return;}if(pos == candidates.size())return;dfs(candidates, target, current, pos + 1); // 跳过当前位置if(target - current >= candidates[pos]){path.push_back(candidates[pos]);dfs(candidates, target, current + candidates[pos], pos);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates, target, 0, 0);return ans;}
};

---

784. 字母大小写全排列

题目链接：https://leetcode.cn/problems/letter-case-permutation/description/

个人解

思路：

• 和上一题类似，当前位置有变 和 不变两种选择

用时：15:00
屎山代码：

class Solution {
public:vector<string> ans;void dfs(string s, int pos){if(pos == s.size()){ans.emplace_back(s);return;}if(!isalpha(s[pos])) // 不是字母{dfs(s, pos + 1);return;}// 当前位置不变dfs(s, pos + 1);// 当前位置改变大小写if (islower(s[pos])) {s[pos] = toupper(s[pos]);} else {s[pos] = tolower(s[pos]);}dfs(s, pos + 1);}vector<string> letterCasePermutation(string s) {dfs(s, 0);return ans;}
};

时间复杂度：$O(2^n)$
空间复杂度：$O(n\times 2^n)$

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！