牛客在线编程101-56 有重复项数字的全排列

港控/mmm° 2023-10-04 20:20 1阅读 0赞

描述  
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 0 < n \\le 80<n≤8 ，数组中的值满足 -1 \\le val \\le 5−1≤val≤5  
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

解析

import java.util.*;
    
    public class Solution {
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        
            ArrayList<Integer> list = new ArrayList<Integer>();
            Arrays.sort(num);
            boolean[] visited = new boolean[num.length];
            Arrays.fill(visited, false);
            dfs(list, num, visited);
            return res;
        }
    
        public void dfs(ArrayList<Integer> list, int[] num, boolean[] visited) {
        
            //dfs边界即一个全排列
            if(list.size() == num.length) {
        
                res.add(new ArrayList<>(list));
                return;
            }
    
            //dfs所有可能
            for(int i = 0; i < num.length; i++) {
        
                //已经使用过的数字
                if(visited[i]) {
        
                    continue;
                }
                //相邻是重复的数字，并且前一个重复的数字已经使用过（保证122只取一次122，其它情况不会取到）
                if(i > 0 && num[i] == num[i-1] && !visited[i-1]) {
        
                    continue;
                }
                //符合选择条件，选择此数
                list.add(num[i]);
                visited[i] = true;
                //递归
                dfs(list, num, visited);
                //回溯
                list.remove(list.size() -  1);
                visited[i] = false;            
            }
        }
    }