题解 | #有重复项数字的全排列#
有重复项数字的全排列
https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型一维数组 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> res = new ArrayList<>(); public ArrayList<Integer> path = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) { boolean[] used = new boolean[num.length]; Arrays.sort(num); bt(num, used, new HashSet<>()); return res; } public void bt(int[] num, boolean[] used, Set<Integer> set) { if (path.size() == num.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < used.length; i++) { if (used[i] || set.contains(num[i])) { continue; } set.add(num[i]); path.add(num[i]); used[i] = true; bt(num, used, new HashSet<>()); // 回溯 used[i] = false; path.remove(path.size() - 1); } } }
回溯算法就是在一颗树上做 dfs,对于每一层已经递归完的数字可以加入到一个 set 集合中,然后在递归前判断是否已经使用过,使用过的话 continue。每次递归的时候都给传一个新的空的 set,因为对于是否有重复数字信息的保存是不需要回溯的,所以直接给一个参数,保证每次开始进入递归时集合都是新的,递归完成回来之后信息不会丢失。