• 39.組合總數(shù)
• 46.全排列—4
• 78.子集
• 79.單詞搜索—1
• 連續(xù)差相同的數(shù)字—1

39.組合總數(shù)

/*** @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  下標(biāo)開始* @param {*} target 剩余目標(biāo)值* @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[][]}*/
// 思路
// 數(shù)量相等
// 剪枝 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四個(gè)方向的或值 并返回
// dfs 什么時(shí)候進(jìn)入
// dfs 返回值 長(zhǎng)度相等時(shí)
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"

連續(xù)差相同的數(shù)字—1

/*** @param {number} n* @param {number} k* @return {number[]}*/
// 思路
// 進(jìn)入下一輪dfs條件
// 首個(gè)或者 絕對(duì)值差為k
// dfs 返回  subset 長(zhǎng)度等于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 不是一個(gè)有效的數(shù)字，因?yàn)樗星皩?dǎo)零。