题解 | 如何理解全排列去除重复的逻辑？

visited[i-1] 的状态，本质是在判断「当前选择相同元素的顺序是否合法」—— 它间接区分了「在路径内延续选择」和「在循环中跳过选择」这两种场景，而后者正是产生重复的根源。

import java.util.*;

public class Solution {

/**

* 生成数组的所有不重复全排列

* @param num int整型一维数组

* @return 所有不重复的全排列

*/

// 存储最终结果

private ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

// 存储当前路径

private ArrayList<Integer> path = new ArrayList<>();

// 回溯算法

private void backTrack(int[] num, boolean[] visited) {

// 如果当前路径长度等于数组长度，说明找到一个完整排列

if (path.size() == num.length) {

// 添加路径的副本，避免后续修改影响已保存的结果

ans.add(new ArrayList<>(path));

return;

}

// 遍历数组元素

for (int i = 0; i < num.length; i++) {

// 如果当前元素已被使用，跳过

if (visited[i]) {

continue;

}

// 处理重复元素：当前元素与前一个元素相同，且前一个元素未被使用时跳过

// 确保相同元素按顺序使用，避免生成重复排列

if (i > 0 && num[i] == num[i - 1] && !visited[i - 1]) {

continue;

}

// 选择当前元素

path.add(num[i]);

visited[i] = true;

// 递归继续寻找下一个元素

backTrack(num, visited);

// 回溯：撤销选择

visited[i] = false;

path.remove(path.size() - 1);

}

}

public ArrayList<ArrayList<Integer>> permute(int[] num) {

// 排序数组，便于处理重复元素

Arrays.sort(num);

boolean[] visited = new boolean[num.length];

backTrack(num, visited);

return ans;

}

}