LeetCode题解:77. 组合,回溯+for循环,JavaScript,详细注释

时间:2021-1-8 作者:admin

原题链接:leetcode-cn.com/problems/co…

解题思路:

该解法参考了46. 全排列的解法LeetCode题解:46. 全排列,回溯,JavaScript,详细注释

  1. 使用DFS生成所有可能的排列情况。
  2. 需要使用used数组,标识每个值是否被使用过,同时used的index即为需要排列的数字。
  3. 清除状态的注意点:
    • 由于subResult和used变量会在每次递归被重复使用,需要注意每次递归后恢复当前状态。
    • 输入: n = 4, k = 2为例,假设是第一层递归,for循环清除状态后每次得到的subResult分别为[1][2][3][4], used分别为[false, true, false, false, false][false, false, true, false, false][false, false, false, true, false][false, false, false, false, true]
    • 也就是说,当subResult为[2]时,上一次循环中所有可能的排列情况都已被输出,而且used所有被使用过的状态都被清除,不会影响当前的递归。
    • 当循环遇到已经使用过的数字,则需要跳过,避免重复排列。
  4. 递归终止时,由于subResult只是一个引用,即它的值会随着函数的运行不断改变,因此需要将其copy一份,否则最终输出的结果都会是[]
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  let result = []; // 存储结果
  let subResult = []; // 存储每次排列的结果
  let used = new Array(n + 1).fill(false); // 通过index对应的布尔值,标识各个值是否被使用,index即代表了从1~n的值

  // 递归生成所有排列
  function dfs(current) {
    // 1. 递归终止条件
    // 当生成排列的长度等于要求的长度,即存储结果,并退出循环
    if (subResult.length === k) {
      // 将当前排列存入结果,需要将原数组copy一份,否则subResult会在for循环结束后被清空
      result.push(subResult.slice());
      return;
    }

    // 利用循环产生不同的排列
    // 假设是第一层递归,for循环每次得到的subResult分别为[1], [2], [3], [4]。
    // 下一层的递归就在第一层的基础上继续进行,同时排除了current之前的值,避免重复排列
    for (let i = current; i < used.length; i++) {
      // 2. 当前层的递归逻辑
      // 如果遇到已被排列过的值,则跳过,避免重复排列
      if (used[i]) {
        continue;
      }
      // 标识当前值已被使用过,并将当前值储存到排列中
      used[i] = true;
      subResult.push(i);
      // 3. 下探到下一层递归
      // 将当前index作为下一层的current,避免重复排列
      dfs(i);
      // 4. 恢复当前层状态
      // 将当前值取消选择
      used[i] = false;
      subResult.pop();
    }
  }
  // 由于该题要求从1开始排列,初始值current为1,过滤掉0
  dfs(1);
  // 返回结果
  return result;
};
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。