回溯算法：求解有不重复和重复元素的全排列问题

回溯算法，求解《剑指 Offer II 083. 没有重复元素集合的全排列》《剑指 Offer II 084. 含有重复元素集合的全排列》《剑指 Offer 17. 打印从1到最大的n位数》

思路

适用问题

• 最优化原理：具备局部最优解

思路

• 确定搜索结构，确保可以覆盖整个空间
• 深度优先搜索（通常用递归实现）
• 确定问题为解决时，回溯

代码模板

46. 全排列

剑指 Offer II 083. 没有重复元素集合的全排列

给定一个不包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

回溯 · 递归版

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  const n = nums.length, r = []
  const d = ar => {
    if (ar.length === n) return r.push(ar.slice())
    for (let i = 0; i < n; i++) {
      if (ar.includes(nums[i])) continue
      ar.push(nums[i])
      d(ar)
      ar.pop()
    }
  }
  d([])
  return r
};

迭代版

var permute = function(nums) {
  const n = nums.length, r = [], stack = [[]]
  while (stack.length) {
    const ar = stack.pop()
    if (ar.length === n) r.push(ar.slice())
    else {
      for (let i = 0; i < n; i++) {
        if (ar.includes(nums[i])) continue
        stack.push(ar.concat(nums[i]))
      }
    }
  }
  return r
};

递归版

var permute = function(nums) {
  const n = nums.length, r = []
  const d = ar => {
    if (ar.length === n) return r.push(ar)
    for (let i = 0; i < n; i++) {
      if (ar.includes(nums[i])) continue
      d(ar.concat(nums[i]))
    }
  }
  d([])
  return r
};

递归版 · 哈希表

哈希表记录访问过的索引

var permute = function(nums) {
  const n = nums.length, r = []
  const d = (ar, visited) => {
    if (ar.length === n) return r.push(ar.slice())
    for (let i = 0; i < n; i++) {
      if (visited[i]) continue
      visited[i] = 1
      ar.push(nums[i])
      d(ar, visited)
      ar.pop()
      visited[i] = 0
    }
  }
  d([], new Uint8Array(n))
  return r
};

例题

47. 全排列 II

剑指 Offer II 084. 含有重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

答案

• 数组升序排列
• 确保重复数字
  • 先填索引小的
  • 再填索引大的

哈希表 · 集合 · Set

var permuteUnique = function(nums) {
  const n = nums.length, r = []
  const d = (ar, visited) => {
    if (ar.length === n) return r.push(ar.slice()) // [...ar] Array.from(ar)
    for (let i = 0; i < n; i++) {
      if (visited.has(i) || i > 0 && nums[i] === nums[i - 1] && !visited.has(i - 1)) continue
      visited.add(i)
      ar.push(nums[i])
      d(ar, visited)
      ar.pop()
      visited.delete(i)
    }
  }
  nums.sort((a, b) => a - b)
  d([], new Set)
  return r
};

哈希表 · 同构数组

var permuteUnique = function(nums) {
  const n = nums.length, r = []
  const d = (ar, visited) => {
    if (ar.length === n) return r.push(ar.slice()) // [...ar] Array.from(ar)
    for (let i = 0; i < n; i++) {
      if (visited[i] || i > 0 && nums[i] === nums[i - 1] && visited[i - 1] === 0) continue
      visited[i] = 1
      ar.push(nums[i])
      d(ar, visited)
      ar.pop()
      visited[i] = 0
    }
  }
  nums.sort((a, b) => a - b)
  d([], new Uint8Array(n))
  return r
};

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

答案

• 数据在安全整数范围 [- (2 ** 53 - 1), 2 ** 53 + 1]，即[Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER]

  var printNumbers = function(n) {
  return Array.from({length: 10 ** n - 1}, (_, i) => i + 1)
  };

• 数据超过安全整数范围

回溯算法

var printNumbers = function(n) {
  const r = []
  const d = (ar, digit) => {
    if (ar.length === digit) return r.push(ar.join(''))
    for (let i = 0; i < 10; i++) {
      if (i === 0 && ar.length === 0) continue
      ar.push(i)
      d(ar, digit)
      ar.pop()
    }
  }
  for (let i = 1; i <= n; i++) d([], i)
  return r
};