02、全排列

把几个互不相同的数放进不同位置，只要位置顺序不同，就是新的排列。与组合相比，排列不能用“后面只选更大的下标”来避免重复，因为那样会丢掉合法顺序。

问题与目标

LeetCode 46：全排列的输入元素互不相同。例如 [1,2,3] 有六种排列：

[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

本页只讨论无重复元素。输入包含重复数字、要求数值答案去重时，请阅读全排列 II，不要把两题的输入前提混在一起。

每层决定下一个位置放谁

路径 path 保存当前已填的前几个位置，used[i] 记录第 i 个输入元素是否已被使用。

每一层都扫描全部下标，跳过已经使用的元素；选中一个后标记、加入路径、递归，然后撤销。这与“从 start 开始扫描”的组合不同：下一位置可以选择任意尚未使用的下标，而不仅是当前下标之后的元素。

为什么回溯不是撤销答案

先选 1，再选 2，再选 3，得到 [1,2,3]，把路径复制到结果。撤销 3 和 2 后，当前路径回到 [1]，就能尝试 3 开头的后半段，得到 [1,3,2]。

撤销只改变正在构建的路径和 used 标记，已经复制到结果中的排列不会随之消失。路径长度达到 n 时才是完整答案，不能把中途的 [1] 当作排列返回。

C++17 实现

#include <vector>

class Solution {
 public:
  std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> answers;
    std::vector<int> path;
    std::vector<bool> used(nums.size(), false);
    search(nums, used, path, answers);
    return answers;
  }

 private:
  void search(const std::vector<int>& nums, std::vector<bool>& used,
              std::vector<int>& path, std::vector<std::vector<int>>& answers) {
    if (path.size() == nums.size()) {
      answers.push_back(path);
      return;
    }
    for (std::size_t i = 0; i < nums.size(); ++i) {
      if (used[i]) continue;
      used[i] = true;
      path.push_back(nums[i]);
      search(nums, used, path, answers);
      path.pop_back();
      used[i] = false;
    }
  }
};

复杂度与边界

n 个不同元素有 n! 种排列，每种复制 n 个元素，时间 O(n·n!)，答案空间 O(n·n!)。不包含答案的路径、标记和调用栈共 O(n)。

本实现不会改动输入数组。对题目范围之外的空输入，返回 [[]]；如果输入有重复值，本实现可能产生重复答案，它没有宣称支持第47题的去重要求。

常见误区

不能用“路径里是否已有这个数值”代替使用下标的思考，否则在拓展到重复值问题时容易出错。也不能把组合的 start = i + 1 原样搬过来；区分“元素只用一次”和“元素只能按下标递增选择”，是这类题的核心。