今日学习

组合总和

题目链接/文章讲解：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()
    }
}