题解 | #有重复项数字的全排列#

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    
    // 定义一个 ArrayList，用于存放最终的返回结果
    ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
    // 定义一个整型变量，用于存放 num 数组的长度
    int lg = 0;
    
    // 系统定义好的函数
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        if (1 == num.length) { // 如果 num 数组的长度为 1，直接返回即可
            ArrayList<Integer> tmp = new ArrayList<>(); // 创建一个一维的 ArrayList
            tmp.add(num[0]); // 然后将 num 的 0 下标位置上的数字加入到 tmp 中
            rs.add(tmp);
            return rs; // 返回结果
        }
        Arrays.sort(num); // 记得给 num 数组先进行排序
        // 定义一个一维的 ArrayList
        ArrayList<Integer> tmp = new ArrayList<>();
        // 定义一个一维的 ArrayList，用于存放 num 数组中的数据
        ArrayList<Integer> nums = new ArrayList<>();
        // 通过增强 for 循环将 num 数组中的数据添加到 ArrayList 中去
        for (int i : num) {
            nums.add(i);
        }
        // 别忘了给 lg 赋值
        lg = nums.size();
        // 调用自定义的递归函数
        process(nums, tmp);
        return rs;
    }
    
    // 自定义的递归函数
    public void process(ArrayList<Integer> num, ArrayList<Integer> tmp) {
        if (lg == tmp.size()) { // 如果 tmp 的长度等于 num 数组的长度
            if (!isContains(rs, tmp)) { // rs 中要不包含 tmp 对象，才把 tmp 对象添加到结果集中，否则不添加
                ArrayList<Integer> trs = new ArrayList<>(); // 重新开辟一块内存空间
                for (int i : tmp) { // 将 tmp 中存放的数据复制一份
                    trs.add(i);
                }
                rs.add(trs);
            }
            return; // 直接返回
        }
        // 遍历 num 数组，依次与 tmp 进行组合
        for (int i = 0; i < num.size(); i++) {
            tmp.add(num.get(i)); // 获取 num 数组中的一个数字，与 tmp 进行组合
            // 再定义一个 ArrayList
            ArrayList<Integer> al = new ArrayList<>();
            for (int j : num) { // 复制一份 num 数组
                al.add(j);
            }
            // 删除指定索引位置上的数字
            al.remove(i);
            process(al, tmp); // 调用递归函数
            tmp.remove(tmp.size() - 1); // 回溯
        }
    }
    
    // 自定义一个函数，用于判断二维的 ArrayList 中是否包含一个一维的 ArrayList
    public boolean isContains(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tmp) {
        if (0 == result.size()) { // 如果 result 为空，那么直接返回 false 即可
            return false;
        }
        for (ArrayList<Integer> i : result) { // 从二维的 ArrayList 中获取一个一维的 ArrayList
            if (isEqual(i, tmp)) {
                return true;
            }
        }
        return false;
    }
    
    // 自定义一个函数，用于判断两个数组是否相等
    public boolean isEqual(ArrayList<Integer> num1, ArrayList<Integer> num2) {
        for (int i = 0; i < num1.size(); i++) {
            if (num1.get(i) != num2.get(i)) {
                return false;
            }
        }
        return true;
    }
}