【回溯】目标和 字母大小全排列

494. 目标和

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

---

解题思路：回溯

​ 这道题我们在背包问题专题就遇到过，其实用回溯来解决这道题是更简单的，不像动态规划那么复杂，但是缺点就是时间复杂度肯定要高得多，这没办法！不过我们是回溯专题，所以就用回溯来求解这道题！

​ 其实这道题用回溯并不难，就是一个暴力搜索，因为对于一个 nums 数组，每个元素我们可以看作两个选择：nums[i] 和 -nums[i]。然后我们只要递归遍历这两种选择对于所有元素的所有路径，最后判断符合要求的就累加次数即可！

​ 下面是算法步骤：

1. 函数头的设计：

   • 首先我们需要一个 全局变量 ret，来存放结果集，至于为什么作为全局变量，前面强调很多次了，就是简化函数头的参数。

   • 然后因为我们需要知道当前遍历到哪个元素了，所以需要一个 局部 index 变量来标识下标！

   • 最后还需要一个 局部变量 path，存放当前路径的运算结果！这道题其实将 path 设为全局变量的话，我们就要写冗余的代码，并且会超时，所以这里干脆将其作为函数参数进行传递即可！

     void dfs(vector<int>& nums, int target, int index, int path);
     

2. 函数体的内容：

   • 函数体很简单，就是递归正负数两种情况：

     dfs(nums, target, index + 1, path + nums[index]); // 正数处理
     dfs(nums, target, index + 1, path - nums[index]); // 负数处理
     

3. 递归函数出口：

   • 当下标遍历超出数组范围了，则此时判断一下此时运算结果是否符合要求，然后进行返回即可：

     // 递归函数出口
     if(index == nums.size())
     {if(path == target)ret++;return;
     }
     

​ 完整代码如下所示：

class Solution {int ret;  // 存放结果集
public:int findTargetSumWays(vector<int>& nums, int target) {dfs(nums, target, 0, 0);return ret;}void dfs(vector<int>& nums, int target, int index, int path){// 递归函数出口if(index == nums.size()){if(path == target)ret++;return;}dfs(nums, target, index + 1, path + nums[index]); // 正数处理dfs(nums, target, index + 1, path - nums[index]); // 负数处理}
};

784. 字母大小写全排列

784. 字母大小写全排列

​ 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

​ 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]

提示:

• 1 <= s.length <= 12
• s 由小写英文字母、大写英文字母和数字组成

---

解题思路：回溯

​ 相信做了这么多回溯练习，这道题就不会很难了，其实也就是一个排列的问题！

​ 根据题意，对于数字字符来说，它只有一种选择，就是直接添加到结果集中，没有其它的路径可以选择！而对于字母字符来说就不一样了，它是有两条路径可以选择的，第一条就是它本身，假如它是小写的话，那么第二条路径就是它的大写的情况！

​ 综上所述，对于数字字符我们只需要进行一次三部曲操作（即处理当前节点、递归、回溯处理），而 对于字母字符来说则需要进行两次三部曲操作，如下图所示：

​ 然后剩下要注意的就是对于字母字符进行第二次三部曲操作之前，要先将第一次三部曲操作的回溯处理完成了，再进行第二次三部曲操作，不然会影响结果的！

​ 剩下的都是一样的！

class Solution {
private:vector<string> ret; // 存放结果集string path;        // 存放当前路径字符的字符串
public:vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}void dfs(string& s, int index){// 递归函数出口if(index == s.size()){ret.push_back(path);return;}// 进行一次处理当前节点、递归path.push_back(s[index]);dfs(s, index + 1);// 如果是字母的话，则要再处理其对应大小写的另一条路径if(s[index] < '0' || s[index] > '9'){path.pop_back(); // 先把上面那次递归的结果进行回溯处理if(s[index] >= 'a' && s[index] <= 'z')path.push_back(s[index] - 32);elsepath.push_back(s[index] + 32);dfs(s, index + 1);}// 进行回溯处理path.pop_back();}
};