请求解释全排列递归代码及递归树生成逻辑

问题背景 #

无法理解这段全排列代码中第一个最左叶子节点完成后，index和j的更新过程；同时疑惑如果将index初始化为j会导致所有元素自交换的问题，结合输入nums = [1,2,3]的输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]，需要详细解释代码逻辑。

代码实现 #

class Solution {
private:
    void solve(vector<int> nums, vector<vector<int>> &ans, int index){
        if(index >= nums.size()){
            ans.push_back(nums);
            return;
        }
        for(int j = index; j < nums.size(); j++){
            swap(nums[index], nums[j]);
            solve(nums, ans, index + 1);
            // 回溯恢复状态
            swap(nums[index], nums[j]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        int index = 0;
        solve(nums, ans, index);
        return ans;
    }
};

核心逻辑：回溯法生成全排列 #

这段代码用回溯+递归的思路生成全排列，核心是：依次将每个元素固定在当前位置，递归处理剩余位置的元素，完成递归后回溯恢复数组状态，继续尝试下一个元素的固定。

分步拆解（以nums = [1,2,3]为例） #

1. 初始调用：solve([1,2,3], ans, 0)

此时index=0，表示要固定第0位的元素，j从0开始遍历到末尾：

• j=0：交换nums[0]和nums[0]（自交换，数组不变），调用solve([1,2,3], ans, 1)
  • 进入index=1的递归，要固定第1位元素，j从1开始：
    • j=1：交换nums[1]和nums[1]，调用solve([1,2,3], ans, 2)
      • 进入index=2的递归，j从2开始：
        • j=2：交换nums[2]和nums[2]，调用solve([1,2,3], ans, 3)
          • 此时index=3 >= nums.size()，将[1,2,3]加入ans，返回上一层
        • 回溯：交换nums[2]和nums[2]（数组不变），j循环结束，返回上一层
    • j=2：交换nums[1]和nums[2]，数组变为[1,3,2]，调用solve([1,3,2], ans, 2)
      • index=2时，j=2交换后调用递归，index=3时将[1,3,2]加入ans，返回
      • 回溯：交换nums[1]和nums[2]，数组回到[1,2,3]，j循环结束，返回上一层
  • 回溯：交换nums[0]和nums[0]，数组不变
• j=1：交换nums[0]和nums[1]，数组变为[2,1,3]，调用solve([2,1,3], ans, 1)
  • 重复类似逻辑，会生成[2,1,3]和[2,3,1]并加入ans，回溯后数组回到[1,2,3]
• j=2：交换nums[0]和nums[2]，数组变为[3,2,1]，调用solve([3,2,1], ans, 1)
  • 重复类似逻辑，会生成[3,2,1]和[3,1,2]并加入ans，回溯后数组回到[1,2,3]

2. 关于index和j的关键说明

• index表示当前要固定的位置：每递归一次index+1，意味着前index位已经固定，接下来处理后面的位置。
• j从index开始遍历：是为了让index位之后的每个元素，都有机会被交换到index位，从而生成不同的排列组合。如果把index初始化为j，相当于每次只处理当前j的位置，无法覆盖所有排列可能，反而会因为重复自交换导致无效操作。
• 回溯的swap：虽然solve函数中的nums是值传递（每次递归都会复制数组），但回溯交换是为了让当前函数的nums恢复到交换前的状态，确保下一次j循环时，交换的是原始数组的元素，避免之前的交换影响后续循环。

内容的提问来源于stack exchange，提问作者Sachin Nigam