90. Subsets II

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

Subsets II - LeetCode

 

중복될 수 있는 정수가 포함된 목록의 모든 하위 목록을 반환하는 문제다.

일전에 풀었던 문제와 비슷하지만, 목록의 조건이 다르다. (중복)

 

그렇기 때문에 선 정렬 후 이전 문제와 동일한 방법으로 풀면 되는데.. 속도는 느린것 같다 ㅎ..

---

class Solution {
public:
    void solve(vector<int>& nums, vector<int>& v, int index) {
        if (find(ret_.begin(), ret_.end(), v) == ret_.end())
            ret_.push_back(v);
        for (int i=index; i<nums.size(); ++i) {
            v.push_back(nums[i]);
            solve(nums, v, i + 1);
            v.pop_back();
        }
    }
 
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> subset;
 
        for (int i=0; i<nums.size(); ++i) {
            solve(nums, subset, i);
            subset.clear();
        }
 
        return ret_;
    }
private:
    vector<vector<int>> ret_;
};

---