LeetCode全排列II传值与传引用解法运行差异原因咨询

两种解法的去重逻辑生效前提完全不同，值传递+无回溯的写法恰好匹配了你写的去重条件，而引用传递+回溯的写法破坏了去重条件的生效前提，具体分析如下：

1. 可正常运行的解法（值传递、无回溯）逻辑 #

你给helper函数传递的是值类型的nums，进入函数时会复制一份独立的数组副本，所有修改仅作用于该副本，且你注释了回溯交换的步骤：

• 每次循环处理下标i时，交换index和i位置的元素后，本地的数组副本会保留这个修改，不会回滚。
• 当i递增到下一个位置时，如果当前位置的元素和现在index位置的元素相同，就会被你的去重条件拦截跳过。
  举个实际例子验证：输入[1,2,2]，进入index=0层时本地副本为[1,2,2]：
  • i=0：交换后数组无变化，递归结束后副本仍为[1,2,2]。
  • i=1：nums[1]=2和nums[0]=1不相等，交换0和1位置，副本变为[2,1,2]，递归结束后不回滚，副本保持[2,1,2]。
  • i=2：此时nums[0]的值已经是2，nums[2]的值也是2，触发if(i!=index && nums[i]==nums[index])条件直接跳过，不会重复处理。
    这种运行逻辑下你的去重条件完全生效，不会产生重复排列。

2. 运行异常的解法（引用传递、有回溯）逻辑 #

你给helper函数传递的是引用类型的nums，所有层操作的是同一份数组，且你加了回溯交换的步骤，每次处理完i都会将数组恢复到当前层的初始状态：

• 每次循环处理完i之后，数组都会被回滚到进入当前层时的初始状态，导致下一次i循环时，index位置的元素始终是初始值，不会因为之前的交换发生变化。
  还是用[1,2,2]举例验证，进入index=0层时初始数组为[1,2,2]：
  • i=0：交换后递归，回溯后数组恢复为[1,2,2]。
  • i=1：nums[1]=2和nums[0]=1不相等，交换0和1位置后递归，回溯后数组又变回[1,2,2]。
  • i=2：此时nums[0]还是初始的1，nums[2]是2，不触发去重条件，会再次执行交换操作，产生和i=1时完全重复的排列结果。
    这就是异常的核心原因：回溯恢复状态的操作，导致你当前的去重逻辑无法识别同一层后续出现的相同可选元素，从而产生大量重复排列。

解法2的修复方案 #

如果要保留引用传递+回溯的写法，需要修改去重逻辑，确保同一层相同的元素只会被处理一次：

for(int i=index; i<nums.size(); i++){
    // 新增判断：index到i之间已经出现过nums[i]的话就跳过，避免重复
    bool duplicate = false;
    for(int j=index; j<i; j++){
        if(nums[j] == nums[i]){
            duplicate = true;
            break;
        }
    }
    if(duplicate) continue;
    swap(nums, i, index);
    helper(nums, index+1);
    swap(nums, i, index);
}

内容的提问来源于stack exchange，提问作者daddys boiii