39 组合总和
题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ
一开始自己写的大概和答案差不多，但是弄不明白回溯要传递的参数，但是自己一开始想到了终止条件，如果>7了就不对了，=7才对，<7就继续加
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
let res = [];
let path = [];
const backTracking = (start,sum) => {
// let sum = 0;
//终止条件
if(sum >= target){
if(sum === target){
res.push(path.slice());
}
return;
}
//单层循环
for(let i = start;i<candidates.length;i++){
path.push(candidates[i]);
//如果把sum的计算写在外面，由于回溯，在下面也要撤销
//也可以直接写成backTracking(i,sum+candidates[i]);
sum += candidates[i];
// 基于此继续选择，传i，下一次就不会选到i左边的数（但会选到i,也就是会选到自己）
//传i+1就不会选到自己了
//从自己本身开始，不选到左边的数据，也是一种剪枝
backTracking(i,sum);
sum -= candidates[i];
path.pop();
}
}
backTracking(0,0);
return res;
};
40 组合总和Ⅱ
题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A
本题一开始给的candidates可能会包含重复的元素，这一点我一开始忽视了，导致我以为和39题基本一致，只需要在for循环的的回溯用i+1即可，但是给出的答案是包含重复组合的。
这道题目和39.组合总和 (opens new window)如下区别：
本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates
最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
强调一下，树层去重的话，需要对数组排序！
本题相较于39只需要改动以下三点：
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
let res = [];
let path = [];
candidates.sort((a,b) => a-b);
const backTracking = (start,sum) => {
//终止条件
if(sum >= target){
if(sum === target){
res.push(path.slice());
return;
}
return;
}
//单词循环逻辑
for(let i = start;i<candidates.length;i++){
if (i - 1 >= start && candidates[i - 1] == candidates[i]) { // 当前选项和左邻选项一样，跳过
continue;
}
path.push(candidates[i]);
backTracking(i+1,sum+candidates[i]);
path.pop();
}
}
backTracking(0,0);
return res;
};
131 分割回文串
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6
/**
* @param {string} s
* @return {string[][]}
*/
//判断是不是回文字符串
const isPalindrome = (s,l,r) => {
for(let i = l,j = r;i<j;i++,j--){
if(s[i] !== s[j]) return false;
}
return true;
}
var partition = function(s) {
const res = [];
const path = [];
function backTracking(start){
//终止条件，start代表切割符号，start走到最后了，那也就结束了
if(start >= s.length){
// res.push(Array.from(path));
res.push(path.slice());
return;
}
for(let i = start;i<s.length;i++){
//需要判断的是[start,i]这个区间内截取的子串
//如果不是回文子串则跳过本次循环
if(!isPalindrome(s,start,i)) continue;
path.push(s.slice(start,i+1));
//寻找i+1为起始位置的子串
//注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1
backTracking(i+1);
path.pop();
}
}
backTracking(0);
return res;
};