回溯算法中去重的另一种写法

用 全排列 II 来进行举例,但是需要注意的是：使用 set 去重的版本相对于 used 数组的版本效率都要低很多。

全排列 II

• 使用数组

var permuteUnique = function (nums) {
  const res = []; // 存储所有唯一的排列结果
  nums = nums.sort((a, b) => a - b); // 对数组进行排序，方便后续去重
  const dfs = (path, used) => {
    if (path.length === nums.length) {
      // 如果当前路径长度等于nums长度，说明找到一个完整排列
      res.push([...path]); // 将当前路径的副本添加到结果集中
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      // 遍历nums数组
      if (used[i]) continue; // 如果当前元素已经被使用，跳过
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // 去重：如果当前元素和前一个元素相同且前一个元素未被使用，跳过
      path.push(nums[i]); // 将当前元素添加到路径中
      used[i] = true; // 标记当前元素为已使用
      dfs(path, used); // 递归调用dfs
      path.pop(); // 回溯：移除路径中的最后一个元素
      used[i] = false; // 回溯：标记当前元素为未使用
    }
  };
  dfs([], []); // 初始调用dfs，路径为空，所有元素未被使用
  return res; // 返回所有唯一排列的结果集
};

• 使用set

function permuteUnique(nums) {
  const resArr = []; // 存储结果的数组
  const usedArr = []; // 标记元素是否被使用的数组
  backTracking(nums, []); // 开始回溯
  return resArr; // 返回结果数组
  function backTracking(nums, route) {
    if (nums.length === route.length) {
      resArr.push([...route]);
      return;
    }
    const usedSet = new Set(); // 用于记录当前层级已经使用过的元素
    for (let i = 0, length = nums.length; i < length; i++) {
      // 如果元素已经被使用过或者当前层级已经使用过该元素，跳过
      if (usedArr[i] === true || usedSet.has(nums[i])) continue;
      usedSet.add(nums[i]); // 记录当前层级使用的元素
      route.push(nums[i]); // 将元素加入当前路径
      usedArr[i] = true; // 标记元素为已使用
      backTracking(nums, route); // 递归调用回溯函数
      usedArr[i] = false; // 回溯，标记元素为未使用
      route.pop(); // 回溯，移除路径中的最后一个元素
    }
  }
}