全排列

题面

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入： nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入： nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

输入： nums = [1] 输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

分析

• 很经典的回溯问题，需要注意，对于排列问题，每个元素是可以被后面的遍历过程使用的，因此不需要使用 startIndex，而是使用 used 来表示哪个数字已经被使用过，以避免数字被重复使用

  • 回溯结束条件：path 长度等于数组长度，即到达叶子节点
  • 何时加入答案：到达叶子节点时加入
  • 回溯之前：标识 i 已经遍历过，path 加入当前元素
  • 回溯操作：弹出当前加入的元素，并取消对 i 的遍历过的标识

• 代码实现

  class Solution {
  public:
      vector<vector<int>> res;
      vector<int> path;
      void backtracking(vector<int>& nums, vector<bool> used) {
          if (path.size() == nums.size()) {
              res.push_back(path);
              return;
          }
          for (int i = 0; i < nums.size(); i++) {
              if (used[i])
                  continue;
              used[i] = true;
              path.push_back(nums[i]);
              backtracking(nums, used);
              path.pop_back();
              used[i] = false;
          }
      }
      vector<vector<int>> permute(vector<int>& nums) {
          vector<bool> used = vector(nums.size(), false);
          backtracking(nums, used);
          return res;
      }
  };

包含重复数字的全排列

• 如果包含重复数字，那么就必须进行去重操作，要先对数组进行排序

  class Solution {
  public:
      vector<vector<int>> res;
      vector<int> path;
      void backtracking(vector<int>& nums, vector<bool> used) {
          if (path.size() == nums.size()) {
              res.push_back(path);
              return;
          }
          for (int i = 0; i < nums.size(); i++) {
              // 去重：同一层重复元素直接跳过
              if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                  continue;
              }
              // 元素已使用，跳过
              if(used[i]==true){
                  continue;
              }
              used[i] = true;
              path.push_back(nums[i]);
              backtracking(nums, used);
              path.pop_back();
              used[i] = false;
          }
      }
      vector<vector<int>> permuteUnique(vector<int>& nums) {
          sort(nums.begin(),nums.end());
          vector<bool> used(nums.size(), false);
          backtracking(nums, used);
          return res;
      }
  };

按字典序排列的全排列

• 相比在得到全排列之和再按字典序排列，可以直接按字典序生成全排列

• 核心改进点是：在回溯过程中就按字典序选择数字，而非生成后再排序。具体逻辑是：

  1. 先将原数组排序（保证初始选择的数字是按从小到大的顺序）；
  2. 回溯时，按数组的升序顺序遍历选择数字（而非随机顺序），这样生成的全排列天然就是字典序，无需后续排序

• 代码实现

  class Solution {
  public:
      vector<vector<int>> res;
      vector<int> path;
      
      // 关键修改1：used改为引用传递，避免不必要的拷贝，提升效率
      void backtracking(vector<int>& nums, vector<bool>& used) {
          if (path.size() == nums.size()) {
              res.push_back(path);
              return;
          }
          // 遍历逻辑不变，但因为nums已提前排序，遍历顺序就是升序，生成的排列天然字典序
          for (int i = 0; i < nums.size(); i++) {
              if (used[i])
                  continue;
              used[i] = true;
              path.push_back(nums[i]);
              backtracking(nums, used);
              path.pop_back();
              used[i] = false;
          }
      }
      
      vector<vector<int>> permute(vector<int>& nums) {
          // 关键修改2：先对nums排序，保证回溯时按升序选择数字，生成天然字典序的排列
          sort(nums.begin(), nums.end());
          
          vector<bool> used(nums.size(), false);
          // 关键修改3：used改为引用传递
          backtracking(nums, used);
          
          return res;
      }
  };