今日学习
组合总和
题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ
第一想法
套公式，必须要在sum<target情况下才能继续递归
/**
- @param {number[]} candidates
- @param {number} target
- @return {number[][]}
*/
let path = []
let res = []
let sum = 0
var combinationSum = function (candidates, target) {
path = []
res = []
sum = 0
backtracking(candidates, target, 0)
return res
};
const backtracking = function (candidates, target, startindex) {
if (sum === target) {
res.push([...path])
return
}
for (let i = startindex; i < candidates.length; i++) {
if (sum + candidates[i] <= target) {
path.push(candidates[i])
sum += candidates[i]
backtracking(candidates, target, i)
path.pop()
sum -= candidates[i]
}
}
}
组合总和II
题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A
第一想法
注意读题，和上一题不一样的一点：不能重复。所以要先对数组进行排序，然后把一样的元素舍去一个。
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
let path = []
let res = []
let sum = 0
var combinationSum2 = function (candidates, target) {
path = []
res = []
sum = 0
candidates.sort((a, b) => a - b)
backtracking(candidates, target, 0)
return res
};
const backtracking = function (candidates, target, startindex) {
if (sum === target) {
res.push([...path])
return
}
for (let i = startindex; i < candidates.length; i++) {
if (i > startindex && candidates[i] === candidates[i - 1]) continue
if (sum + candidates[i] <= target) {
path.push(candidates[i])
sum += candidates[i]
backtracking(candidates, target, i + 1)
path.pop()
sum -= candidates[i]
}
}
}
分割回文串
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
第一想法
第一次见这个题还是有点难度，看了视频才有点感觉，分割的过程，包括运用slice把分割开的回文串加入到path里，然后在这一层遍历完所有要素之后再将path push到res里
/**
* @param {string} s
* @return {string[][]}
*/
let path = []
let res = []
const isP = function (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) {
path = []
res = []
backtracing(s, 0)
return res
};
const backtracing = function (s, startindex) {
// 在每一组回溯中如果到底了，那这次回溯就结束，就要输出一组path
if (startindex >= s.length) {
res.push([...path])
return
}
for (let i = startindex; i < s.length; i++) {
if (!isP(s, startindex, i)) continue
path.push(s.slice(startindex, i + 1))
backtracing(s, i + 1)
path.pop()
}
}
