Leetcode - Permutation II [java]

문제 출처: https://leetcode.com/problems/permutations-ii/

문제 설명

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

Example 1:

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

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

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

문제 풀이

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        
        Map<Integer, Integer> allNums = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++) {
            if(!allNums.containsKey(nums[i]))
                allNums.put(nums[i], 0);
            allNums.put(nums[i], allNums.get(nums[i]) + 1);
        }
        List<List<Integer>> answer = new ArrayList<>();
        backtracking(new LinkedList<Integer>(), nums.length, answer, allNums);
        return answer;
    }
    
    public void backtracking (LinkedList<Integer> cur, int target, List<List<Integer>> answer, Map<Integer, Integer> allNums) {
        
        if(target == 0) {
            answer.add(new ArrayList<Integer>(cur));
        } else {
            for(Integer key1 : allNums.keySet()) {
                if(allNums.get(key1) == 0) continue;
                
                allNums.put(key1, allNums.get(key1) - 1);
                cur.addLast(key1);
                backtracking(cur, target - 1, answer, allNums);
                cur.removeLast();
                allNums.put(key1, allNums.get(key1) + 1);
            }
        }
    }
}

중복이 들어간 숫자의 순열을 찾아야하는 문제이다.

중복이 없는 순열과 다른점은 중복이 없다면 단순히 boolean 배열의 tracker를 하나 만들어서 backtracking 해주면 되지만 이 문제는 중복 처리를 위해 HashMap을 사용하는 것이 포인트이다.

[1,1,2,3]의 배열을 중복 distict numbers만 포함하는 숫자 배열의 순열을 구하는 알고리즘을 구현하면

모든 부분집합이 중복으로 나온다.

ex)

첫번째 1 + 두번째 1 + 2 + 3
두번째 1 + 첫번째 1 + 2 + 3

하지만 hashmap으로 key는 숫자, value는 빈도로 변환처리를 하면

key 1 : value 2
key 2 : value 1
key 3 : value 1

key값을 순회하기 때문에 같은 숫자가 여러개 있더라도 중복을 모두 배제 시킨다.