算法| 回溯

• 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-1

var 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 不是一个有效的数字，因为它有前导零。