代码随想录二刷|第七章：回溯算法

startIndex来记录下一层递归，搜索的起始位置。
如果没有startIndex，输出的结果将会是[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
剪枝：
已选择的元素个数：path.size()，还需要的元素个数：k - path.size()，在集合n中至多从i = n - (k - path.size()) + 1开始遍历：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)

本题：传入sum
剪枝：
1、

if (sum > targetSum) { // 剪枝操作return;
}

2、

for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝

1、把string放进path里可以用 path += string，可是怎么拿出来呢？pop_back()
也不用+=，用push_back(i)，但这个i必须是char类型的
2、我的错误：当我尝试使用 digits[startIndex] 作为键时，实际上是用字符（如 ‘2’，‘3’ 等）而不是整数。因此需要先- ‘0’。
3、可以不用map，直接用数组
4、传入index：用来记录遍历到第几个数字，同时也表示树的深度。

集合内元素不重复，但是可以重复取用
1、我应该添加一个条件来确保递归调用在 sum 超过 target 时停止。否则会无限递归。
216.组合总和III这道题即使不加这个也不会无限递归，因为它的子集个数必须是k，而本题对子集个数没有限制。
2、虽然本题可以重复取值，但依然要用startIndex，因为它是保证树层上的去重的，而startIndex = i + 1才是树枝上去重的。
剪枝：（要先排序）
排序之后，如果下一层的sum（即本层的sum + candidates[i]）大于target，就不进入下一层递归

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

集合中有重复元素，并且不可以重复取用
1、排序+used数组：保证没有两个组合是相同的

本质上还是组合问题
1、切割线用什么表示？可以用i吗？不可以，就是用startIndex
2、切割的长度用什么表示？可以也用i吗？不可以，[startIndex, i]就是要截取的子串
3、递归如何终止？
优化：
动态规划思想：给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。
isPalindrome[i][j] 代表 si:j是否是回文字串

1、pointNum：用于记录添加".“的数量，本题不需要真的切割出子串，在原本的字符串上添加”."即可
2、终止条件：本题不能用切割线切到最后为终止条件，因为字符串只会分为4段
3、如何判断每一段是否合法？

    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;}

4、往字符串里加入、删除不用push_back、pop_back，因为不是单个字符，用insert、erase

收集树形结构中每一个节点的结果，因此不需要任何剪枝！
1、怎么把根节点[]放进去？
把收集子集 result.push_back(path);放在终止条件的上面
2、终止条件：

if (startIndex >= nums.size()) {return;
}

其实可以不加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。

集合中有重复元素，并且不可以重复取用

1、不排序也可以用used数组吗？不能！！使用set来对本层元素进行去重
为什么递归函数上面的uset.insert(nums[i]);，下面却没有对应的pop之类的操作？而used数组中就需要？
这是因为unordered_set uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！而used数组一直是同一个。
2、怎么保证递增？
nums[i] >= path.back() 不是path.top()

if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}

3、终止条件：

if (path.size() > 1) {result.push_back(path);// 注意这里不要加return，因为要取树上的所有节点
}

优化：
不用set，用数组来做去重操作：
int used[201] = {0}; // 题目说数值范围[-100, 100]
数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组。

1、怎么不取上次已取的？怎么避免这种情况：[[0,0],[0,1],[1,0],[1,1]]
使用used数组，记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
这里的used数组和前面的排序+used数组的作用不一样。

集合中有重复元素，并且不可以重复取用
1、怎么样把上面的used数组两种作用结合起来？

组合问题：
如果是一个集合来求组合的话，就需要startIndex。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

排列问题：
for不是从startIndex开始，而是从0开始了。
怎么不重复取本次排列里的元素？used数组

集合中有重复元素：
树枝去重：同一个组合内不能有重复的元素
树层去重：同一组合内可以重复，但两个组合不能相同（排序+used数组）

组合问题和分割问题：
收集叶子节点的结果
子集问题：
收集树的所有节点的结果