import java.util.*; public class Solution { /** * 给出一组可能包含重复项的数字,返回该组数字的所有排列。结果以字典序升序排列。 * */ /*相对字典有序*/ //用于标记是否访问过 boolean []mark; public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { //存储总的返回结果集 ArrayList<ArrayList<Integer>> res = new ArrayList<>(); //存储一个合法全排列 LinkedList<Integer> track = new LinkedList<>(); mark = new boolean[num.length]; //因为存在重复项,为了更好的处理,将数组先排序 Arrays.sort(num); Dfs(num, res, track); return res; } public void Dfs(int[] num, ArrayList<ArrayList<Integer>> res, LinkedList<Integer> track) { //若 找到一个全排列,则将它加进结果集中,然后返回(回溯) if (track.size() == num.length) { res.add(new ArrayList<Integer>(track)); return; } for (int i = 0; i < num.length; i++) { // (1)当此时的被访问过,可跳过 // (2)当i>0 &&此时的数等于它的上一个&&上一个没访问过(没访问过证明是回溯后将前面的置为false,所以此时避免重复得用 !mark[i-1] 满足要求然后跳过该数字) if (mark[i] || i > 0 && num[i] == num[i - 1] && !mark[i - 1]) { continue; } //添加进全排列数组中 track.add(num[i]); //标记为已经访问 mark[i] = true; //继续寻找下一个数 Dfs(num, res, track); //将上一次全排列的结果中,最后一个数移除掉 track.removeLast(); //移除掉的数置为 未访问 mark[i] = false; } } }
解题思想:dfs套路,主要是重复元素跳过逻辑。