《算法题讲解指南：递归，搜索与回溯算法--综合练习》--14.找出所有子集的异或总和再求和，15.全排列Ⅱ，16.电话号码的字母组合，17.括号生成

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录14.找出所有子集的异或总和再求和题目链接题目描述题目示例解法(递归)算法思路C算法代码算法总结及流程解析15.全排列Ⅱ题目链接题目描述题目示例解法算法思路C算法代码算法总结及流程解析16.电话号码的字母组合题目链接题目描述题目示例解法算法思路C算法代码算法总结及流程解析17.括号生成题目链接题目描述题目示例解法算法思路C算法代码算法总结及流程解析结束语14.找出所有子集的异或总和再求和题目链接1863. 找出所有子集的异或总和再求和 - 力扣LeetCode题目描述题目示例解法(递归)算法思路所有子集可以解释为:每个元素选择在或不在一个集合中(因此子集有2”个)。本题我们需要求出所有子集将它们的异或和相加。因为异或操作满足交换律所以我们可以定义一个变量直接记录当前状态的异或和。使用递归保存当前集合的状态(异或和)选择将当前元素添加至当前状态与否并依次递归数组中下一个元素。当递归到空元素时表示所有元素都被考虑到记录当前状态(将当前状态的异或和添加至答案中)。例如集合中的元素为[1,2]则它的子集状态选择过程如下[ ]/ \[ ] [1] //第一个元素选择与否/ \ / \[ ] [2] [1] [1, 2] //第二个元素选择与否每个状态到这⼀层时需要记录异或和递归函数设计void dfs(int val,int idx, vectorint nums)参数val(当前状态的异或和)idx(当前需要处理的元素下标处理过程选择将其添加至当前状态或不进行操作);返回值无;函数作用选择对元素进行添加与否处理。递归流程:1.递归结束条件当前下标与数组长度相等即已经越界表示已经考虑到所有元素;a.将当前异或和添加至答案中并返回;2.考虑将当前元素添加至当前状态当前状态更新为与当前元素值的异或和然后递归下一个元素;3.考虑不选择当前元素当前状态不变直接递归下一个元素;C算法代码class Solution { public: int ret 0; int sum 0; int subsetXORSum(vectorint nums) { dfs(nums, 0); return ret; } void dfs(vectorint nums, int index) { ret sum; for(int i index; i nums.size(); i) { sum ^ nums[i]; dfs(nums, i 1); //回溯-恢复现场(nums[i]^nums[i]0) sum ^ nums[i]; } } };算法总结及流程解析15.全排列Ⅱ题目链接47. 全排列 II - 力扣LeetCode题目描述题目示例解法算法思路因为题目不要求返回的排列顺序因此我们可以对初始状态排序将所有相同的元素放在各自相邻的位置方便之后操作。因为重复元素的存在我们在选择元素进行全排列时可能会存在重复排列例如:[1,2,1]所有的下标排列为012021102120201210按照以上对应的下标进行排列的结果为121112211211112121可以看到有效排列只有三种[1,1,2][1,2,1][2,1,1]其中每个排列都出现两次。因此我们需要对相同元素定义一种规则使得其组成的排列不会形成重复的情况1.我们可以将相同的元素按照排序后的下标顺序出现在排列中通俗来讲若元素s出现x次则排序后的第2个元素s一定出现在第1个元素s后面排序后的第3个元素s一定出现在第2个元素s后面以此类推此时的全排列一定不会出现重复结果。2.例如a11a21a32排列结果为[1,1,2]的情况只有一次即a1在a2 前面因为 a2 不会出现在a1前面从而避免了重复排列。3.我们在每一个位置上考虑所有的可能情况并且不出现重复;4.*注意*若当前元素的前一个相同元素未出现在当前状态中则当前元素也不能直接放入当前状态的数组此做法可以保证相同元素的排列顺序与排序后的相同元素的顺序相同即避免了重复排列出现。5.通过深度优先搜索的方式不断地枚举每个数在当前位置的可能性并在递归结束时回溯到上一个状态直到枚举完所有可能性得到正确的结果。递归函数设计void backtrack(vectorint nums, int idx)参数idx(当前需要填入的位置);返回值无;函数作用查找所有合理的排列并存储在答案列表中。递归流程如下1.定义一个二维数组ans用来存放所有可能的排列一个一维数组 perm 用来存放每个状态的排列一个一维数组visited 标记元素然后从第一个位置开始进行递归2.在每个递归的状态中我们维护一个步数idx表示当前已经处理了几个数字3.递归结束条件:当idx等于nums数组的长度时说明我们已经处理完了所有数字将当前数组存入结果中4.在每个递归状态中枚举所有下标i若这个下标未被标记并且在它之前的相同元素被标记过则使用 nums数组中当前下标的元素a.将visited[i]标记为 1;b.将 nums[i]添加至 perm 数组末尾;c.对第step1个位置进行递归;d.将visited[i]重新赋值为 0并删除perm末尾元素表示回溯;5.最后返回ans。C算法代码class Solution { public: vectorvectorint ret; bool check[9]; vectorint path; vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(), nums.end()); dfs(nums); return ret; } void dfs(vectorint nums) { if(path.size() nums.size()) { ret.push_back(path); return; } for(int i 0; i nums.size(); i) { //剪枝 if(i 1 check[i - 1] false nums[i -1] nums[i]) { continue; } if(check[i] false) { path.push_back(nums[i]); check[i] true; dfs(nums); //回溯-恢复现场 path.pop_back(); check[i] false; } } } };算法总结及流程解析16.电话号码的字母组合题目链接17. 电话号码的字母组合 - 力扣LeetCode题目描述题目示例解法算法思路每个位置可选择的字符与其他位置并不冲突因此不需要标记已经出现的字符只需要将每个数字对应的字符依次填入字符串中进行递归在回溯是撤销填入操作即可。在递归之前我们需要定义一个字典 phoneMap记录2~9各自对应的字符。递归函数设计void backtrack(unordered_mapchar, string phoneMap, string digits, int index)参数index(已经处理的元素个数)ans (字符串当前状态)res (所有成立的字符串);返回值无函数作用查找所有合理的字母组合并存储在答案列表中。递归函数流程如下1.递归结束条件:当index等于digits 的长度时将 ans 加入到 res 中并返回;2.取出当前处理的数字digit根据 phoneMap取出对应的字母列表letters;3.遍历字母列表letters将当前字母加入到组合字符串ans的末尾然后递归处理下一个数字(传入index 1表示处理下一个数字);4.递归处理结束后将加入的字母从ans的末尾删除表示回溯。5.最终返回 res即可。C算法代码class Solution { public: vectorstring ret; string path; unordered_mapchar, string hash; vectorstring letterCombinations(string digits) { hash[2] abc; hash[3] def; hash[4] ghi; hash[5] jkl; hash[6] mno; hash[7] pqrs; hash[8] tuv; hash[9] wxyz; // dfs(digits, digits[0], 0); dfs(digits, 0); return ret; } // void dfs(string digits, char num, int index) // { // if(path.size() digits.size()) // { // ret.push_back(path); // return; // } // for(int i 0; i hash[num].size(); i) // { // path.push_back(hash[num][i]); // dfs(digits, digits[index 1], index 1); // //回溯-恢复现场 // path.pop_back(); // } // } //优化参数 void dfs(string digits, int index) { if(path.size() digits.size()) { ret.push_back(path); return; } for(int i 0; i hash[digits[index]].size(); i) { path.push_back(hash[digits[index]][i]); dfs(digits, index 1); //回溯-恢复现场 path.pop_back(); } } };算法总结及流程解析17.括号生成题目链接22. 括号生成 - 力扣LeetCode题目描述题目示例解法算法思路从左往右进行递归在每个位置判断放置左右括号的可能性若此时放置左括号合理则放置左括号继续进行递归右括号同理。一种判断括号是否合法的方法:从左往右遍历左括号的数量始终大于等于右括号的数量并且左括号的总数量与右括号的总数量相等。因此我们在递归时需要进行以下判断1.放入左括号时需判断此时左括号数量是否小于字符串总长度的一半(若左括号的数量大于等于字符串长度的一半时继续放置左括号则左括号的总数量一定大于右括号的总数量);2.放入右括号时需判断此时右括号数量是否小于左括号数量。递归函数设计void dfs(int step, int left)参数step(当前需要填入的位置)left(当前状态的字符串中的左括号数量);返回值无;函数作用查找所有合理的括号序列并存储在答案列表中。递归函数参数设置为当前状态的字符串长度以及当前状态的左括号数量递归流程如下1.递归结束条件:当前状态字符串长度与2*n相等记录当前状态并返回;2.若此时左括号数量小于字符串总长度的一半则在当前状态的字符串末尾添加左括号并继续递归递归结束撤销添加操作;3.若此时右括号数量小于左括号数量(右括号数量可以由当前状态的字符串长度减去左括号数量求得)则在当前状态的字符串末尾添加右括号并递归递归结束撤销添加操作;C算法代码class Solution { public: int left 0; int right 0; vectorstring ret; string path; vectorstring generateParenthesis(int n) { dfs(n); return ret; } void dfs(int n) { //有效括号的组合条件 //(1)左括号数量右括号数量 //(2)以开头为起始位置的任意子串-左括号数量右括号数量 if(path.size() 2 * n) { if(left n right n) { ret.push_back(path); } return; } path.push_back((); left; //左括号剪枝 if(left n) { dfs(n); } //回溯-恢复现场 path.pop_back(); left--; path.push_back()); right; //右括号剪枝 if(left right) { dfs(n); } //回溯-恢复现场 path.pop_back(); right--; } };算法总结及流程解析结束语到此14.找出所有子集的异或总和再求和15.全排列Ⅱ16.电话号码的字母组合17.括号生成 这四道算法题就讲解完了。子集异或总和通过递归枚举元素选/不选两种状态计算所有子集异或和。全排列II在排序基础上通过剪枝避免重复排列使用标记数组记录已选元素。电话号码字母组合 递归处理数字映射构建所有可能的字母组合。括号生成通过左右括号数量约束确保合法性递归构建有效括号组合。希望大家能有所收获