Permutations Backtracking Template

用 used[] 标记元素是否已使用的回溯模板。

#resource / algorithm #type / snippet #status / evergreen #algo / backtracking

[!info] related notes 算法面试题型 MOC 回溯

Permutations Backtracking Template

核心：

path 维护当前选择序列
used[i] 标记 nums[i] 是否已被选进 path
path.length == n 时收集答案

JavaScript Snippet

var permute = function(nums) {
  const res = [];
  const path = [];
  const n = nums.length;
  const used = new Array(n).fill(false);

  function dfs() {
    if (path.length === n) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  }

  dfs();
  return res;
};

回溯