Java Code Implementation For All Unique Permutations

-
This is a common question asked in interviews of Microsoft, Google & Facebook. You might have stumbled upon this question in LeetCode or InterviewBit.

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Here is the working solution for this problem in Java. It uses backtracking to solve the problem.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> currentResult = new ArrayList<Integer>();
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        int startPosition = 0;
        calculate(nums, startPosition, results);
        return results;
    }
    
    private void calculate(int[] nums, int startPosition, 
                           List<List<Integer>> results) {
        if(startPosition == nums.length - 1){
            List<Integer> currentResult = new ArrayList<Integer>();
            for(int num : nums){
                currentResult.add(num);
            }
            results.add(currentResult);
        }
        else {
            Set<Integer> usedNumbers = new HashSet<Integer>();
            for(int i = startPosition; i < nums.length; i++){
                if(usedNumbers.contains(nums[i])){
                    continue;
                } else {
                    usedNumbers.add(nums[i]);
                    swap(nums, startPosition, i);
                    calculate(nums, startPosition + 1, results);
                    //backtracking
                    swap(nums, startPosition, i);
                }
            }
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Time complexity in O(n!).
T(n) = n * T(n-1)
T(n-1) = (n-1) * T(n-2)
T(n-2) = (n-2) * T(n-3)
As you can see time complexity becomes n * (n-2) * (n - 3) ... * 1 which is O(n!).

Comments

Post a Comment