[👍][BackTrack][Medium] 90. Subsets II

https://leetcode.com/problems/subsets-ii/description/

 

정수 배열이 주어 질 때, 가능한 한 모든 sub set을 찾아라. 

이때 중복이 없도록 하라.

 

subset 1과 기본적으로 동일하지만, input에 중복값이 주어진다. 

따라서 결과에서는 주어진 input을 제외하고 다른 중복이 있으면 안된다. 

1, 2

2, 1 등은 허용하지 않는다. 

 

1과 기본적으로 같은 흐름으로 하되, 

결과에 중복만 set으로 filter 해 보았다. 

 

코드

void subsetsWithDupBT(int idx, vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& nums, unordered_set<string>& sBuff)
{
    string temp;
    for(int q = 0; q < vCur.size(); ++q)
        temp += (to_string(vCur[q]) + "_");

    if(sBuff.find(temp) == sBuff.end())
    {
        vRet.push_back(vCur);
        sBuff.insert(temp);
    }
    if (idx >= nums.size())
        return;

    for (int q = idx; q < nums.size(); ++q)
    {
        vCur.push_back(nums[q]);
        subsetsWithDupBT(q + 1, vRet, vCur, nums, sBuff);
        vCur.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) 
{
    sort(nums.begin(), nums.end());
    vector<vector<int>> vRet;
    vector<int> vCur;
    unordered_set<string> sBuff;
    subsetsWithDupBT(0, vRet, vCur, nums, sBuff);
    return vRet;
}

 

 

결과

 

속도는 예상외로 괜찮게 나왔다.

하지만, string을 써서 set을 사용한 것이 조금 효율적이지 않게 느껴진다. 

 

 

이 문제의 backtrack이 값을 쌓아 나가는 과정을 유심히 살펴 보자.

 

1, 2a, 2b, 3  - 2가 중복값이라고 가정하고, 구분을 위해 2a, 2b로 두었다. 

 

위 backtrack 로직을 가동하면, 

0    1        2           3                 4                   - backTrack Func idx

[] - [1] - [1,2a] - [1,2a,2b] - [1,2a,2b,3]          - 0

                      - [1,2a,3]                                 - 1

         - [1,2b]  - [1,2b,3]                                - 2

    -[2a]-[2a,2b]-[2a,2b,3]                              - 3

           -[2a,3]                                               - 4

    -[2b]-[2b,3]                                               - 5

    -[3]                                                            - 6

 

모든 back track으로 만들 수 있는 조합 가운데, 

위 붉은 색의 경우 중복으로 더 이상 진행 할 필요가 없음을 알았다.

 

문제는, 어떻게 저 경우는 걸러 내느냐 하는 것일 것이다. 

보면, 추가하려는 대상값이 그 직전 값과 같고,

backTrack()에서 인자로 넘어오는 index가 for로 인해 증가할 때, 문제가 생기는 것을 알 수 있다.

 

따라서 if( iter_idx > backtrack_index && nums[iter_idx-1] != nums[iter_idx]) 

일때 더 이상 진행을 하지 않으면 될 것이다. 

 

코드 

void subsetsWithDupBT(int idx, vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& nums)
    {
        vRet.push_back(vCur);
        if (idx >= nums.size())
            return;
        
        for (int q = idx; q < nums.size(); ++q)
        {
            // 이 경우 중복이 생기므로, 제외한다.
            if(q>idx && nums[q-1]==nums[q])
                continue;
            
            vCur.push_back(nums[q]);
            subsetsWithDupBT(q + 1, vRet, vCur, nums);
            vCur.pop_back();
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vRet;
        vector<int> vCur;
        subsetsWithDupBT(0, vRet, vCur, nums);
        return vRet;
    }

 

 

결과