Concise JAVA solution based on DFS


  • 3

    The basic idea is using DFS to put possible numbers to each i position, use boolean visited[] to flag the visited nodes, so that avoid accessing the same node many times. The tricky part of this problem is the solution for duplicated numbers: in the same position, only put one distinct number once.

    For i position, there're (n-i) possibilities, so the total possilities are: n(n-1)(n-2)..1 = O(n!):**

    Time complexity = O(n!)

    public LinkedList<List<Integer>> permuteUnique(int[] A) {
    	 LinkedList<List<Integer>>res = new LinkedList<List<Integer>>();
    	 Arrays.sort(A);//Sort the array first
    	 DFS(A, new LinkedList<Integer>(), new boolean[A.length], res);
    	 return res;
     }
     void DFS(int[] A,  LinkedList<Integer>solution, boolean visited[], LinkedList<List<Integer>>res) {
    	 if (solution.size() == A.length) {
    		 res.add(new LinkedList<Integer>(solution));
    		 return;
    	 }		  
    	 for (int i = 0; i < A.length; i++) {
    	     //Deal with duplicated numbers, visited[i-1] should be true. (In the same position, only put one distinct number)
    		 if (visited[i] || (i-1 >= 0 && visited[i-1] && A[i] == A[i-1]))
    			 continue; 
    		 visited[i] = true;
    		 solution.add(A[i]);
    		 DFS(A, solution, visited, res);
    		 solution.remove(solution.size()-1);
    		 visited[i] = false;	
    	 }
     }

  • 0
    L

    I felt this is the only working solution on this model of solving :) Thanks. you saved my time


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.