Leetcode - 47. Permutations II

문제

중복된 수가 포함될 수 있는 배열이 주어진다. 이 수로 만들수 있는 permutation의 모든 경우의 수를 구하라.

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

해결 아이디어

• 기존 permutation 해결방법에서 살짝 변형.
• 주어진 배열 값이 몇개가 존재하는지 해시테이블에 저장.
• 백트래킹을 배열을 전부 하는게 아니라 중복된 값이 제거된 수 중에서 backtracking을 수행, 그리고 해당 count값이 0이 되면 백트래킹을 중지.
• 가령 [1,1,2] 의 경우 백트래킹을 1,2만 수행하되, 재귀호출시 table[1]-- 을하고, 함수 호출이 끝나면 table[1]++ 로 복원.
• 백트래킹을 해시테이블로 하는 부분을 힌트 참고. 아주 좋은 솔루션같다.

풀이

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> tmp;
    unordered_map<int, int> count;
    
    void back_tracking(vector<int> nums, int size) {
        if (size < 0)
            return;
        if (size == 0) {
            ret.push_back(tmp);
            return;
        }
        for (auto it: count) { // iterate hashtable ...!
            if (it.second == 0)
                continue;
            
            count[it.first]--;
            tmp.push_back(it.first);
            back_tracking(nums, size - 1);
            tmp.pop_back();
            count[it.first]++;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        for (auto it: nums)
            count[it]++;
        back_tracking(nums, nums.size());
        return ret;
    }
};