文章目录
- 1. 前言
- 2. 算法题
- 22.括号生成
- 494.目标和
- 39.组合总和
- 784.字母大小写全排列
- [526. 优美的排列](https://leetcode.cn/problems/beautiful-arrangement/)
1. 前言
后面的练习是接着下面链接中的文章所继续的，在对后面的题练习之前，可以先将下面的的文章进行了解👇：
【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题（C++）
2. 算法题
22.括号生成
思路
- 题意分析：要求根据给出的数字，算出合法的括号组成个数。根据题目，我们可以总结出下面的规则：
- 解法：dfs + 根据决策树设计递归、回溯、剪枝
- 决策树：
- 根据上图决策树，即可直接着手编写代码：
- 细节问题：
代码
class Solution { public: int left, right, _n; // 分别记录左右括号的数量 vector ret; // 结果数字 string path; vector generateParenthesis(int n) { _n = n; dfs(); return ret; } void dfs() { if(right == _n) // 当前path序列有效，加入结果 { ret.push_back(path); return; } if(left494.目标和
思路
- 题意分析：对于数组给出的数字，通过向所有数字前补加减号，使最后的值为 target
- 解法：dfs + 根据决策树设计递归、回溯、剪枝
- 该解法并非最优解法，但这里依然用dfs做，并引出一些写法问题。
- 决策树：（省略了后面的步骤）
- 根据决策树的思路，不难看出实际上与 题目 78.子集 非常相似，代码也是如此，但有一个需要注意的细节，先看代码：
代码1
class Solution { public: int ret, path, _target; int findTargetSumWays(vector& nums, int target) { _target = target; dfs(nums, 0); // 从0位置开始 return ret; } void dfs(vector& nums, int pos) { // 终止条件 if(pos == nums.size()) { if(path == _target) ret++; return; } // 正号 path += nums[pos]; dfs(nums, pos + 1); path -= nums[pos]; // 负号 path -= nums[pos]; dfs(nums, pos + 1); path += nums[pos]; } };- 最开始我们提到，深搜dfs并非该题的最优解法， 时间开销很大，对于上面的代码，更是面临超时的风险，上面的代码将 path作为全局变量
- 我们可以 进行优化：将path作为参数传递
- 更改后的代码，时间开销会小一些
代码2
class Solution { public: int ret, _target; int findTargetSumWays(vector& nums, int target) { _target = target; dfs(nums, 0, 0); // 从0位置开始 return ret; } void dfs(vector& nums, int pos, int path) { // 终止条件 if(pos == nums.size()) { if(path == _target) ret++; return; } // 正号 dfs(nums, pos + 1, path + nums[pos]); // 负号 dfs(nums, pos + 1, path - nums[pos]); } };path定义形式的理由
- 频繁的执行 + - 操作，是一比不小的时间消耗，直接传参可以只需要将计算后的结果直接作为参数递归。
- 而对于 [78.子集]，我们将path定义为全局变量，因为对于该题情况，path 本身为vector类型，作为参数传递会导致频繁的创建vector，不利于节省时间。
39.组合总和
思路
- 题意分析：即通过给定的数组任意分配，组成和为目标值的序列，求序列的种类。
- 解法：dfs + 根据决策树设计递归、回溯、剪枝
解法1
- 决策树：如图所示：
- 即每次分支都进行所有数字的选择，符合条件的继续，由于题目要去重，同层下选过的不再复选
- 剪枝：同层的选过的剪掉 + 该路径和超出目标值或该位置超出数组范围的剪掉
代码
class Solution { public: int _target; vector path; vector ret; vector combinationSum(vector& candidates, int target) { _target = target; dfs(candidates, 0, 0); return ret; } void dfs(vector& nums, int pos, int pathSum) { // 路径和等于目标值，记录结果，向上返回 if(pathSum == _target) { ret.push_back(path); return; } // 路径和大于目标值 / 当前位置超出数组； 向上返回 if(pathSum > _target || pos >= nums.size()) return; for(int i = pos; i解法2
- 决策树：
对于上图，有一个需要注意的细节问题：
- 对于恢复现场：
此时我们可以编写代码：
代码
class Solution { public: int _target; vector path; vector ret; vector combinationSum(vector& candidates, int target) { _target = target; dfs(candidates, 0, 0); return ret; } void dfs(vector& nums, int pos, int pathSum) { // 路径和等于目标值，记录结果，向上返回 if(pathSum == _target) { ret.push_back(path); return; } // 路径和大于目标值 / 当前位置超出数组； 向上返回 if(pathSum > _target || pos >= nums.size()) return; for(int k = 0; k * nums[pos] if(k) path.push_back(nums[pos]); // 枚举 当前值的个数，添加到数组中 dfs(nums, pos + 1, pathSum + k*nums[pos]); } // 恢复现场 for(int k = 1; k * nums[pos] // 将每个元素添加过的个数值 都恢复 path.pop_back(); } } }; public: string path; // 记录当前字母序列 vector dfs(s, 0); return ret; } void dfs(string s, int pos) { if(path.size() == s.size()) { ret.push_back(path); return; } char ch = s[pos]; // 不改变的情况：数字 以及 字母的第一种情况 path += ch; dfs(s, pos + 1); path.pop_back(); if(isalpha(ch)) // 需要改变 { // 改变大小写 if(ch public: bool used[16]; int ret; int countArrangement(int n) { dfs(1, n); // 从下标为1处填n个数 return ret; } void dfs(int pos, int n) { if(pos == n + 1){ // 更新结果 ret += 1; return; } // 全排列 + 判断是否符合优美排列 for(int i = 1; i if(!used[i] && (i % pos == 0 || pos % i == 0)) { used[i] = true; dfs(pos + 1, n); used[i] = false; // 恢复现场 } } } };
- 决策树：
- 决策树：如图所示：
- 题意分析：要求根据给出的数字，算出合法的括号组成个数。根据题目，我们可以总结出下面的规则：
