算法| ss 回溯

• 39.组合总数
• 46.全排列—4
• 78.子集
• 79.单词搜索—1
• 连续差相同的数字—1

39.组合总数

/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
// 思路
// dfs传参，传idx， 剩余target
// dfs返回： =0 收集， <0 false
var combinationSum = function (candidates, target) {const sets = [];const subset = [];dfs(0, target, subset);//   console.log(sets);return sets;/**** @param {*} idx  下标开始* @param {*} target 剩余目标值* @returns*/function dfs(idx, target, subset) {if (target < 0) return;if (target === 0) {sets.push([...subset]);return;}for (let j = idx; j < candidates.length; j++) {subset.push(candidates[j]);dfs(j, target - candidates[j], subset);subset.pop();}}
};
combinationSum([2, 3, 6, 7], 7);

46.全排列—4

/*** @param {number[]} nums* @return {number[][]}*/
// 思路
// 数量相等
// 剪枝 used+ i===i-1var permuteUnique = function (nums) {const sets = [];const subset = [];const used = Array(nums.length).fill(0);dfs(subset);console.log(sets);function dfs(subset) {for (let i = 0; i < nums.length; i++) {if (subset.length === nums.length) {sets.push([...subset]);return;}if (used[i] === 1) continue;if (i > 0 && nums[i] === nums[i - 1] && used[i - 1] === 1) continue;used[i] = 1;subset.push(nums[i]);dfs(subset);subset.pop();used[i] = 0;}}
};
permuteUnique([1, 1, 2]);
// nums = [1,1,2]

78.子集

/*** @param {number[]} nums* @return {number[][]}*/
// 思路
// dfs idx传参是依次递增
var subsets = function (nums) {const sets = [];const subset = [];dfs(0, subset);//   console.log(sets);return sets;function dfs(idx, subset) {if (subset.length > nums.length) return;sets.push([...subset]);for (let i = idx; i < nums.length; i++) {subset.push(nums[i]);dfs(i + 1, subset);subset.pop();}}
};
subsets([1, 2, 3]);
// nums = [1,2,3]

79.单词搜索—1

/*** @param {character[][]} board* @param {string} word* @return {boolean}*/
// 思路
// dfs四个方向的或值 并返回
// dfs 什么时候进入
// dfs 返回值 长度相等时
var exist = function (board, word) {const m = board.length;const n = board[0].length;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (board[i][j] === word[0]) {if (dfs(0, i, j)) return true;}}}return false;function dfs(idx, x, y) {if (x < 0 || x >= m || y < 0 || y >= n) return false;if (board[x][y] !== word[idx]) return false;if (idx === word.length - 1) return true;board[x][y] = null;const res =dfs(idx + 1, x + 1, y) ||dfs(idx + 1, x - 1, y) ||dfs(idx + 1, x, y + 1) ||dfs(idx + 1, x, y - 1);board[x][y] = word[idx];return res;}
};console.log(exist([["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E", "E"],],"ABCCED")
);
console.log(exist([["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E", "E"],],"ABCB")
);
// board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
// [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

连续差相同的数字—1

/*** @param {number} n* @param {number} k* @return {number[]}*/
// 思路
// 进入下一轮dfs条件
// 首个或者 绝对值差为k
// dfs 返回  subset 长度等于n  并且首位不能为0
var numsSameConsecDiff = function (n, k) {const sets = [];const subset = [];dfs(subset);// console.log(sets);return sets;function dfs(subset) {for (let i = 0; i < 10; i++) {if (subset.length === n) {if (subset[0] !== 0) {sets.push(+subset.join(""));}return;}if (subset.length === 0 ||Math.abs(subset[subset.length - 1] - i) === k) {subset.push(i);dfs(subset);subset.pop();}}}
};
numsSameConsecDiff(3, 7);// 输入：n = 3, k = 7
// 输出：[181,292,707,818,929]
// 解释：注意，070 不是一个有效的数字，因为它有前导零。