문제 출처: 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]]
Example 2:
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값을 순회하기 때문에 같은 숫자가 여러개 있더라도 중복을 모두 배제 시킨다.
