【算法day17-day18】回溯：解决组合问题

不好意思呀各位，最近在忙期末考今天才彻底结束，来让我们继续算法之路吧~

题目引用

---

1. 组合
2. 电话号码的字母组合
3. 组合总和
4. 组合总和II
5. 分割回文串

1.组合

---

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

我们来看这道回溯入门题，首先呢我要说一下我对回溯的想法，在我看来回溯其实就是在不断递归的过程中形成了一颗多叉树，那么它是个树，我们就可以对其的路径进行记录，剪枝，判断等等一系列操作，从而形成一系列的结果集合。
拿这道题目举例，我们创建一个全局的res用于记录结果，path用于记录多叉树的每一条路径，创建一个递归函数，先设定函数的出口：当我们记录的path.size()==k时，就说明已经得到一种结果了，将path加入到结果数组中。那么递归函数的主体就是把1到n的数都遍历一遍，在每条路径中加入当前数值，再递归下一个元素，返回后pop掉。这其实就是记录树的路径，在前些天讲二叉树时已经讲过了。
那么来看代码：

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(int n,int k,int startIndex){if(path.size()==k){res.push_back(path);return;} for(int i=startIndex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();}return;}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return res;}
};

怎么样，应该比前几天题目简单不少吧。

2.电话号码的字母组合

---

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

来看这道题目，我们乍一眼一看是不是头都大了，不知道怎么才能解决这种问题。不急~只要我们慢慢分析总能分析出个一二三四，首先是电话号码对应的字母，我们肯定需要一个表来进行映射，再就是如果我们使用回溯的思想，那么就要看一下是不是和上一道题相同，不同的话应该怎么修改。
可以确定的是，这题和上一道题是不太一样的。第一、递归出口不一样。第二、每一层所能选择的元素数目和和元素本身的大小是不确定的。但是好在都能够通过遍历一遍字符串，逐层处理，逐层确定。
那么来解决这道题吧。首先，我们不能使用startIndex来确定每一层的开始位置，而是使用Index来作为源字符串内数字的定位，然后通过数字在我们自己写好的表中找到对应的数字代表的字符串，然后这样每一层的元素才确定了下来，再去回溯就很简单的解决了。
来看代码：

class Solution {
public:string digitsmap[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> res;string path;void backtracking(string digits,int Index){if(Index==digits.size()){res.push_back(path);return;}int digit=digits[Index]-'0';string letter=digitsmap[digit];for(int i=0;i<letter.size();i++){path+=letter[i];backtracking(digits,Index+1);path.pop_back();}return;}vector<string> letterCombinations(string digits) {if(digits=="") return res;backtracking(digits,0);return res;}
};

这样写，轻轻松松100%啦

3.组合总和

---

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

做完上面那道题，做这道题就是小卡拉米了。需要注意的不过是从数组里面直接取出来和可重复，但是只要把握住这两个点，其实就不会很难。
来看代码：

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates,int targetSum,int sum,int startIndex){if(sum>targetSum) return;if(sum==targetSum){res.push_back(path);return;}for(int i=startIndex;i<candidates.size()&&sum<targetSum;i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,targetSum,sum,i);sum-=candidates[i];path.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return res;}
};

是不是简简单单呀~

4.组合总和II

---

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

我们可以看一下这道题和上一道题目的区别，不可重复且只能使用一次。条件是比较苛刻的，所以我们就自己加一点工具来限制住这个多叉树的发展，其实就有一点点像剪枝了。这里我们加上一个used数组来判断这个数是否被用过，再在递归时将startIndex+1就可以了。
这里来看代码：

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

这里大家是不是对树枝和树层比较困惑呢，因为同一树层使用过说明我之前已经在这个位置取过这个数了，那么我现在再取肯定时重复的，同一树枝取过说明我们这一条路径上有一样的元素，但是并不是重复取的，所以是可以入到path里面的。这样说会不会好一点。

5.分割回文串

---

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
。返回 s 所有可能的分割方案。

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

这道题目就比较难想到了。我们利用startIndex来分割题目给的字符串，分割完以后判断这个字符串是不是回文，是就赋值给path，不是就直接开始下一个循环。判断是不是回文串的方法有很多，我们这里采用我们三周之前学过的二分法来做判断（是不是不记得了）。那么这道题目就做完了。其实这些题目看到答案后都不会觉得很难，但难的是想出答案的过程，而这也是区分大家的过程。
来看代码

class Solution {
public:vector<vector<string>> res;vector<string> path;void backtracking(const string& s,int startIndex){if(startIndex>=s.size()) {res.push_back(path);return;}for(int i=startIndex;i<s.size();i++){if(ispl(s,startIndex,i)){string str=s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back();}}bool ispl(const string& s, int start, int end){for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}vector<vector<string>> partition(string s) {backtracking(s, 0);return res;}
};

总结

---

其实这些题目看到答案后都不会觉得很难，但难的是想出答案的过程，而这也是区分大家的过程。