39.组合总和
题目链接：
https://leetcode.cn/problems/combination-sum/
题目描述：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
思路：
连续几天都在做回溯的题目，回溯的题目思路都比较直接。首先是将问题分解成嵌套的子问题，对子问题的处理构成了回溯函数backtracking，反复地调用backingtracking函数从而解决问题。
本题和组合问题77的不同仅在于数组中的元素可以被重复选取，体现在算法上也就是分解问题的方法不同。
不包含重复数字的组合问题：
包含重复数字的组合问题：
终止条件为选出的数字之和大于或者等于target。
写出代码如下：
var combinationSum = function(candidates, target) {
let res = []
let path = []
let len = candidates.length
for(let i = 0; i < len; i++){
path.push(candidates[i])
backtracking(i, candidates[i])
path.pop()
}
return res
/**
* @param {number} 子问题处理的数组的起始下标
* @param {number} target
*/
function backtracking(start,sum){
//终止条件
if(sum > target){
return
}
else if(sum == target){
res.push([...path])
return
}
//对子问题的子问题进行处理
else{
for(let i = start; i < len; i++){
path.push(candidates[i])
backtracking(i, candidates[i]+sum)
path.pop()
}
}
}
};
40.组合总和Ⅱ
题目链接：
https://leetcode.cn/problems/combination-sum-ii/
题目描述：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
思路：
这道题的难点在于candidates中有重复的元素，如果仍然按照之前的方式分解原问题会导致最后的结果中出现不同顺序的同一组合。
例如：candidates=[1,1,7,1], target=9 结果：[1,1,7]和[1,7,1]
需要进行剪枝去重操作，除去重复元素的产生的部分分支。首先对candidate进行排序，然后在每次分解问题时，相同元素只选取第一个来产生子问题。
使用上述例子，candidate排序后为[1,1,1,7]，将其分解为1+[1,1,7]和7+[]两种情况。因为相同元素选取第一个的情况包括了其他情况。所以这里，1+[1,7]和1+[7]都可以被舍去。
写出代码如下：
var combinationSum2 = function(candidates, target) {
//先将数组进行排序
candidates = candidates.sort((a,b)=>a-b)
let res = []
let path = []
let len = candidates.length
backtracking(0, 0)
return res
/**
* @param {number} 子问题处理的数组的起始下标
* @param {number} target
*/
function backtracking(start,sum){
//终止条件
if(sum > target){
return
}
else if(sum == target){
res.push([...path])
return
}
//对子问题的子问题进行处理
else{
for(let i = start; i < len; i++){
//相同元素只取第一个
if((i-1)>=start && candidates[i] === candidates[i-1]) continue
path.push(candidates[i])
backtracking(i+1, candidates[i]+sum)
path.pop()
}
}
}
};
131.分割回文串
题目链接：
https://leetcode.cn/problems/palindrome-partitioning/
题目描述：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
思路：
套用回溯问题的模板，只不过组合问题变成了切割问题。 在for循环中，i表示的是切割位置，每次添加进path的是下标从start到i的回文字符串。
代码：
var partition = function(s) {
let res = []
let path = []
let len = s.length
backtracking(0)
return res
function backtracking(start){
//终止条件
if(start === len){
res.push([...path])
}
for(let i = start; i < len; i++){
if(check(start, i)){
path.push(s.slice(start,i+1))
backtracking(i+1)
path.pop()
}
}
}
//判断回文(可以使用动态规划提高速度)
function check(start, end){
let left = start
let right = end
while(left < right){
if(s[left++] !== s[right--]) return false
}
return true
}
};