C++ three simple methods


  • 0
    X
    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            vector<vector<int>> ret;
            ret.push_back(vector<int>());
            sort(nums.begin(), nums.end());
            vector<vector<int>> sub;
            for(int i = 0; i < nums.size(); ++i){
                if(i == 0 || nums[i] != nums[i - 1]){
                    sub = ret;
                }
                for(auto& j : sub){
                    j.push_back(nums[i]);
                }
                ret.insert(ret.end(), sub.begin(), sub.end());
            }
            return ret;
        }
    /*
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end(), less<int>());
            vector<int> subset;
            backtrack(0, nums.size(), subset, nums);
            return ans;
        }
    private:
        vector<vector<int>> ans;
        void backtrack(int depth, int n, vector<int>& subset, vector<int>& nums){
            ans.push_back(subset);
            for(int i = depth; i < n; ++i){
                if(i != depth && nums[i] == nums[i - 1]){
                    continue;
                }
                subset.push_back(nums[i]);
                backtrack(i + 1, n, subset, nums);
                subset.pop_back();
            }
        }
    */
    /*
        //backtrack solution using map
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            if(nums.empty()){
                return ans;
            }
            for(int i = 0;i < nums.size(); ++i){
                if(m.find(nums[i]) == m.end()){
                    m[nums[i]] = 0;
                }
                ++m[nums[i]];
            }
            backtrack(m.begin(), m.end(), m);
            return ans;
        }
    private:
        unordered_map<int, int> m;
        unordered_map<int, int> pick;
        vector<vector<int>> ans;
        void backtrack(unordered_map<int, int>::iterator depth, unordered_map<int, int>::iterator n, unordered_map<int, int>& nums){
            if(depth == n){
                vector<int> subset;
                for(auto it = pick.begin(); it != pick.end(); ++it){
                    int tmp = it->second;
                    while(tmp--){
                        subset.push_back(it->first);
                    }
                }
                ans.push_back(subset);
                return;
            }
            auto tmp = depth;
            ++tmp;
            for(int j = 0; j <= (depth->second); ++j){
                pick[depth->first] = j;
                backtrack(tmp, n, nums);
            }
        }
    */
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.