目录
1.找出所有子集的异或总和再求和
题解
⭕2.全排列 II
题解
3.电话号码的字母组合
题解
1.找出所有子集的异或总和再求和
链接：1863. 找出所有子集的异或总和再求和
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
- 例如，数组
[2,5,6]的 异或总和 为2 XOR 5 XOR 6 = 1。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
示例 1：
输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6题解
- 先找出所有子集
- 然后把每个子集异或的和加起来返回去。
算法原理：
这道题和我们上一道思路完全是一模一样，
- 先画出决策树
- 设计代码
- 全局变量
- 递归函数
- 细节：回溯、剪枝、递归出口
因为我们有上一道题的基础，我们直接就画出决策树
这里我们需要两个全局变量
- 一个path记录到沿途每个子集的异或
- 然后sum负责每个字节的异或和加起来。
dfs函数，还是需要一个pos记录当前异或的位置，dfs(nums,pos)，回溯利用异或的规则，两个相同的数异或为0。
- 这里也没有剪枝， 递归出口 循环结束就是递归出口。
class Solution {
public:int path=0;int ret=0;int subsetXORSum(vector<int>& nums) {//八个子集 异或和dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){ret+=path; //放在循环外for(int i=pos;i<nums.size();i++){path ^=nums[i];dfs(nums,i+1);//通过 i 来处理path ^=nums[i];//huan yuan}}
};⭕2.全排列 II
链接：47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]题解
- 重复的数全排列后会有重复的结果
- 这道题就是要求去掉重复 之后的全排列
算法原理：
这道题几乎和全排列1 一模一样，我们就不在细说那些决策树怎么画，代码应该怎么写等等。
这里主要就是剪枝的问题。
- 下面我们边画决策树变分析问题，把全排列所有不重复不漏的情况画出来，越详细越好。
- 例如 [1,1,1,2]
- 我们只用关心四个位置，每个位置每次从数组中4个数选择一个树放到一个位置上就行了。
只用选四次就行了。
- 第一次可以选第一个1、第二个1、第三个1、2，但是注意这里就存在剪枝的问题了，如果第一个位置还把第二个1和第三个1选上，此时就会存在重复问题！因为后面三个位置是从112中选的。
此时就出现了第一种剪枝情况
- 同一个节点的所有分支中，相同的元素只能选择一次
然后我们再往下走，第二个位置也可以从数组中4个数字中选任意一个。
- 但是第一个1我们要把它剪掉，因为第一个位置已经把第一个1选过了，只能选一次。
- 此时就有了第二种剪枝情况，这个是和全排列1一模一样的。
同一个位置的数，相同的数 只能使用一次
- 还是用bool类型的check数组可以实现，check[i] = true 表明已经使用过了，
- check[i] = false 说明还没有使用过。
但是这里还会出现剪枝情况，第一个1不能用，那我可以把第二个1放在第二个位置
但是第三个1不能出现了，因为同一个节点分支，相同的数只能出现一次
接下来我们就不画了，我们就可以写代码了。代码逻辑和全排列1几乎一模一样，这里我们主要分析，剪枝应该怎么写。
剪枝可以从两个角度写。其实就是两个if判定语句。
- 1.只关心 “不合法” 的分支。 不合法的直接不让递归下去
- 2.只关心 “合法” 的分支 合法的就递归
虽然是两个角度，但是最终得到结果都是一样的。
只关心 “不合法” 的分支
- 当有一个位置已经选了这个数了下一个位置就不能在选这个位置，check[i] == true
- 属于同一个分支节点，前面的数和当前的数相等 就不能选当前的数了。nums[i] == nums[i-1]，因此这个条件最终是 i != 0 && nums[i] == nums[i-1] && check[i-1] == false
把上面两个条件组合在一起就得到只关心 “不合法” 的分支
只关心 “合法” 的分支
- 首先是要 没被选过， 当一个数没人选的时候可以选这个数 check[i] == false
- 还要满足 3 个中的一个
-
- 首节点 i==0
- 和前一个节点不一样 num[i]!=num[i-1]
- 前一个已经被选过了 check[i-1]==true
3.电话号码的字母组合
链接：17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
题解
- 就是数字对应的字符串进行排列组合。
- 对于这种搜索啊、暴搜啊，我们已经知道要用到递归，回溯、剪枝了。
有了前面的基础，这个题我们就不写那么步骤了，画出决策树，我们直接写出对应需要的东西。
- 不过在此之前我们需要先将数字与字符串映射关系搞和，我们可以用哈希表映射
- 或者其他方法，这里最简单的就是弄一个字符串数组把数字和字符串映射一下。
接下来就是画出决策树然后分析一下
- 首先需要两个全局变量 ret记录结果，path记录每条路径到叶子节点的组合
- 递归函数 给我一个digits和数字然后递归函数把组合后的结果返回出来，相信它一定能完成任务。dfs(digits,pos)
- 然后回溯 记得恢复现场，递归出口 到叶子节点，这道题没有剪枝。
class Solution {
public:vector<string> ret;string path;vector<string> hash={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> letterCombinations(string digits) {if (digits.empty()) return {}; // 处理空输入的特殊情况dfs(digits,0);return ret;}void dfs(string digits,int pos){if(path.size()==digits.size()){ret.push_back(path);return;}int num = digits[pos] - '0';for (char c : hash[num]) {path.push_back(c);dfs(digits,pos+1); //pos+1 实现移动path.pop_back();}}
};
