LeetCode Java Solutions

47. Permutations II

Medium

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

Example

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

Solution

Use BackTracking and Recursion to solve the problem.

public List<List<Integer>> permuteUnique(int[] nums) {
        Map<Integer,Integer> countMap = new HashMap<>();
        for(int i=0; i< nums.length; i++){
            countMap.put(nums[i],countMap.getOrDefault(nums[i],0)+1);
        }
        List<List<Integer>> output = new ArrayList<>();
        int[] numArray = new int[countMap.size()];
        int[] count = new int[countMap.size()];
        Set<Integer> keyset = countMap.keySet();
        int index=0;
        for(Integer val : keyset){
            Integer countVal = countMap.get(val);
            numArray[index]=val;
            count[index]=countVal;
            index++;
            
        }
        int[] result = new int[nums.length];
        calculaltePermutation(numArray, count,result, 0, output);
        return output;
        
    }
    
public void calculaltePermutation(int[] numArray, int[] count, int[] result, int level, List<List<Integer>> output){
        if(level == result.length){
            List<Integer> levelResult = new ArrayList<>();
            for(int res:result){
                levelResult.add(res);
            }
            output.add(levelResult);
        }
        for(int i=0; i< numArray.length; i++){
            if(count[i]==0){
                continue;
            }
            result[level]=numArray[i];
            count[i]--;
          calculaltePermutation(numArray,count,result,level+1,output);
            count[i]++;
        }
    }