39. 组合总和
解题思路：
1. 回溯算法
这道题可以利用sum来逐层计算。注意的点在于for循环内部调用递归的时候需要从i开始，这代表了可以重复读取当前的数。
var combinationSum = function (candidates, target) {
const result = [];
const path = [];
const backtracking = (candidates, target, sum, startIndex) => {
if (sum > target) {
return;
}
if (sum === target) {
result.push(Array.from(path));
return;
}
for (let i = startIndex; i < candidates.length; i++) {
sum += candidates[i];
path.push(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop();
}
}
backtracking(candidates, target, 0, 0);
return result;
};
2. 剪枝优化
- 可以在for循环里面加一个 sum + candidates[i] <= target，用来控制大于target的数。
- 注意这里还需要对原数组排序 candidates.sort((a, b) => a - b)， 不然就无法保证每次加的都是最大值。
var combinationSum = function (candidates, target) {
const result = [];
const path = [];
const backtracking = (candidates, target, sum, startIndex) => {
if (sum > target) {
return;
}
if (sum === target) {
result.push(Array.from(path));
return;
}
for (let i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop();
}
}
candidates.sort((a, b) => a - b);
backtracking(candidates, target, 0, 0);
return result;
};
40. 组合总和 II
解题思路：
这道题的难点在于去重的逻辑，需要满足条件：
i > 0 && candidates[i] === candidates[i - 1] && used[i - 1] === false
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过。
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过。
- 对于相等的值要对同一树层使用过的元素进行跳过，树枝上面的元素不需要跳过。
var combinationSum2 = function (candidates, target) {
const path = [];
const result = [];
const used = new Array(candidates.length).fill(false);
const backtracking = (candidates, target, sum, startIndex, used) => {
if (sum > target) {
return;
}
if (sum === target) {
result.push(Array.from(path));
return;
}
for (let i = startIndex; i < candidates.length; i++) {
if (i > 0 && candidates[i] === candidates[i - 1] && used[i - 1] === false) {
continue;
}
sum += candidates[i];
path.push(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);
sum -= candidates[i];
path.pop();
used[i] = false;
}
}
candidates.sort((a, b) => a - b)
backtracking(candidates, target, 0, 0, used);
return result;
};
131. 分割回文串
解题思路：
这道题有两个关键问题，一个是切割，一个是判断回文。
对于切割线，可以用startIndex来表示下一轮递归遍历的起始位置，这也就是切割线。实际上 [startIndex, i] 就是每次截取的子串。
对于判断回文，可以用双指针来判断。
const isPalindrome = (s, startIndex, i) => {
let left = startIndex;
let right = i;
while (left < right) {
if (s[left] === s[right]) {
left++;
right--;
} else {
return false;
}
}
return true;
}
var partition = function (s) {
const path = [];
const result = [];
const backtracking = (s, startIndex) => {
if (startIndex >= s.length) {
result.push(Array.from(path));
return;
}
for (let i = startIndex; i < s.length; i++) {
if (!isPalindrome(s, startIndex, i)) {
continue;
}
path.push(s.slice(startIndex, i + 1));
backtracking(s, i + 1);
path.pop();
}
}
backtracking(s, 0);
return result;
};
