回溯的应用之数组全排列

回溯模板

function backtrack(path) {
  if (结束条件) {
    return;
  }
  for (循环条件) {
    // 添加数据
    path.add(数据);
    // 递归调用
    backtrack(path);
    // 移除数据
    path.remove(数据);
  }
  return ans;
}
JavaScript

代码实现

/**
 * 全排列
 * @param {any[]} arr 数组
 * @returns
 */
function permute(arr) {
  const ans = [];
  const used = Array(arr.length);
  function backtrack(path) {
    if (path.length === arr.length) {
      ans.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      path.push(arr[i]);
      used[i] = true;
      backtrack(path);
      path.pop();
      used[i] = false;
    }
    return ans;
  }
  return backtrack([]);
}
JavaScript

测试

console.log(permute([1, 2, 3]));
// [
//   [ 1, 2, 3 ],
//   [ 1, 3, 2 ],
//   [ 2, 1, 3 ],
//   [ 2, 3, 1 ],
//   [ 3, 1, 2 ],
//   [ 3, 2, 1 ]
// ]
JavaScript