131.分割回文串
题目链接：. - 力扣（LeetCode）
讲解视频：131.分割回文串
题目描述：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
解题思路：
深度：由当前字符串所含字母个数决定。当递归至字符串末尾即startIdx==字符串s长度时返回
宽度：由当前字符串所含字母个数决定。使用startIdx和i来确定子串范围。若子串不是回文串，就continue
代码：
class Solution {
public:vector<vector<string>> result;vector<string> path;bool isPalindromicString(string sub){for(int i = 0, j = sub.size()-1; i<j; i++,j--)if(sub[i] != sub[j]) return false;return true;}void Backtracking(string s, int startIdx){if(startIdx == s.size()){result.push_back(path);return;}for(int i = startIdx; i < s.size(); i++){string sub = s.substr(startIdx,i - startIdx + 1);if(isPalindromicString(sub)){path.push_back(sub);}else continue;Backtracking(s,i+1);path.pop_back();}}vector<vector<string>> partition(string s) {Backtracking(s,0);return result;}
};93.复原IP地址
题目链接：. - 力扣（LeetCode）
讲解视频：
回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址
题目描述：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
解题思路：
深度：以‘.’的个数作为深度，最多3个‘.’，深度最大为3（根深度为0）
宽度：本题中宽度最多为3。而且截取出的数需满足题目要求
剪枝：同一层中当子串满足如下任意一个条件时该层就停止遍历：
- 以0开头且长度不为1
- 长度>=3且值超过255
代码：
class Solution {
public:vector<string> result;bool isValid(string s, int start, int end){if(start > end) return false;if(s[start] == '0' && start != end) return false;int sum = 0;for(int i = start; i <= end; i++){char c = s[i];if(c < '0' || c > '9') return false;sum = sum*10 + (c - '0');if(sum > 255) return false;}return true;}void backTracking(string& s, int startIdx, int pointSum){if(pointSum == 3){if(isValid(s,startIdx, s.size()-1)) result.push_back(s);return;}for(int i = startIdx; i < s.size(); i++){if(isValid(s,startIdx,i)){s.insert(s.begin()+i+1,'.');pointSum++;backTracking(s,i+2,pointSum);pointSum--;s.erase(s.begin()+i+1);}else break;}}vector<string> restoreIpAddresses(string s) {result.clear();if(s.size() < 4 || s.size() > 12) return result;backTracking(s,0,0);return result;}
};78.子集
题目链接：. - 力扣（LeetCode）
讲解视频：
回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集
题目描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解题思路：
与分割题类似，唯一不同点在于该题目除根节点以外的节点都要保存，之前做的题只保存叶子节点
代码：
class Solution {
public:vector<vector<int>> result;vector<int> path;void backTracking(vector<int>& nums, int startIdx){result.push_back(path);if(startIdx >= nums.size()) return ;for(int i = startIdx; i < nums.size(); i++){path.push_back(nums[i]);backTracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {result.clear();backTracking(nums,0);return result;}
};90.子集II
题目链接：. - 力扣（LeetCode）
讲解视频：
回溯算法解决子集问题，如何去重？| LeetCode：90.子集II
题目描述：
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解题思路：
该题目是要在前一题的基础上增加去重操作，同一棵树相同元素不去重，不同子树同一层相同元素要去重。有如下两种方法：
- set去重-->根据set中不会保存重复元素的特点，对不同子树同一层重复元素进行去重
- used数组去重-->方法同回溯组合篇--代码随想录算法训练营第二十一天的40.组合总和II题
代码：
1、set方法
class Solution {
public:vector<vector<int>> result;vector<int> path;void backTracking(vector<int>& nums, int startIdx){result.push_back(path);if(startIdx >= nums.size()) return;unordered_set<int> isdup;for(int i =startIdx; i < nums.size(); i++){if(isdup.find(nums[i]) != isdup.end()) continue;path.push_back(nums[i]);isdup.insert(nums[i]);backTracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(),nums.end());backTracking(nums,0);return result;}
};2、used数组判断法
class Solution {
public:vector<vector<int>> result;vector<int> path;void backTracking(vector<int>& nums, int startIdx, vector<int>& used){result.push_back(path);if(startIdx >= nums.size()) return;for(int i =startIdx; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0) continue;path.push_back(nums[i]);used[i] = 1;backTracking(nums,i+1,used);used[i] = 0;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();path.clear();vector<int> used(nums.size(),0);sort(nums.begin(),nums.end());backTracking(nums,0,used);return result;}
};
