【回溯】目标和 字母大小全排列
文章目录
- 494. 目标和
- 解题思路：回溯
- 784. 字母大小写全排列
- 解题思路：回溯
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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
解题思路：回溯
这道题我们在背包问题专题就遇到过，其实用回溯来解决这道题是更简单的，不像动态规划那么复杂，但是缺点就是时间复杂度肯定要高得多，这没办法！不过我们是回溯专题，所以就用回溯来求解这道题！
其实这道题用回溯并不难，就是一个暴力搜索，因为对于一个 nums 数组，每个元素我们可以看作两个选择：nums[i] 和 -nums[i]。然后我们只要递归遍历这两种选择对于所有元素的所有路径，最后判断符合要求的就累加次数即可！
下面是算法步骤：
-
函数头的设计：
-
首先我们需要一个 全局变量
ret，来存放结果集，至于为什么作为全局变量，前面强调很多次了，就是简化函数头的参数。 -
然后因为我们需要知道当前遍历到哪个元素了，所以需要一个 局部
index变量来标识下标！ -
最后还需要一个 局部变量
path，存放当前路径的运算结果！这道题其实将path设为全局变量的话，我们就要写冗余的代码，并且会超时，所以这里干脆将其作为函数参数进行传递即可！void dfs(vector<int>& nums, int target, int index, int path);
-
-
函数体的内容：
-
函数体很简单，就是递归正负数两种情况：
dfs(nums, target, index + 1, path + nums[index]); // 正数处理 dfs(nums, target, index + 1, path - nums[index]); // 负数处理
-
-
递归函数出口：
-
当下标遍历超出数组范围了，则此时判断一下此时运算结果是否符合要求，然后进行返回即可：
// 递归函数出口 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 <= 12s由小写英文字母、大写英文字母和数字组成
解题思路：回溯
相信做了这么多回溯练习，这道题就不会很难了，其实也就是一个排列的问题！
根据题意，对于数字字符来说，它只有一种选择，就是直接添加到结果集中，没有其它的路径可以选择！而对于字母字符来说就不一样了，它是有两条路径可以选择的，第一条就是它本身，假如它是小写的话，那么第二条路径就是它的大写的情况！
综上所述，对于数字字符我们只需要进行一次三部曲操作（即处理当前节点、递归、回溯处理），而 对于字母字符来说则需要进行两次三部曲操作，如下图所示：
然后剩下要注意的就是对于字母字符进行第二次三部曲操作之前，要先将第一次三部曲操作的回溯处理完成了，再进行第二次三部曲操作，不然会影响结果的！
剩下的都是一样的！
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);
else
path.push_back(s[index] + 32);
dfs(s, index + 1);
}
// 进行回溯处理
path.pop_back();
}
};