题解 | JAVA 递归+回溯 #有重复项数字的全排列# [P0]

跟这题一样，还是暴力递归+回溯。只不过多记录个上次选择的数, 然后skip掉所有duplicates.

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
      // sort to insure output in alphabet order, and to help skip duplicate
      Arrays.sort(num);
      // copy sorted nums to remain
      ArrayList<Integer> remain = new ArrayList<>();
      for (int n : num) remain.add(n); 
      
      permuteRec(remain, new ArrayList<>());
      return ans;
    }
  
    public void permuteRec(ArrayList<Integer> remain, ArrayList<Integer> perm) {
      // base case, i.e. no remaining elem
      if (remain.isEmpty()) {
        ans.add(new ArrayList<>(perm));
        return;
      }
      
      int lastA = -2; // 因为数字范围是 [-1. 5]
      for (int i = 0; i < remain.size(); i++) {
        Integer a = remain.get(i);
        if (a.equals(lastA)) continue; // skip duplicated choices
        else lastA = a;
        
        perm.add(remain.remove(i));
        permuteRec(remain, perm);
        
        // 复原 (a.k.a 回溯)
        remain.add(i, a);
        perm.remove(perm.size()-1);
      }
    }
}