[recommend for beginners]clean C++ implementation with detailed explanation


  • 2

    This is my implementation, to check the duplicate cases, i use the

      unordered_set<vector<int>> 
    

    to filter the duplicate cases. But my code can not compile oK!

    Here is the compiling error info:

     required from ‘struct std::__and_<std::__is_fast_hash<std::hash<std::vector<int, std::allocator<int> > > >, std::__detail::__is_noexcept_hash<std::vector<int, std::allocator<int> >, std::hash<std::vector<int, std::allocator<int> > > > >’
    

    Code:

    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            int _size=nums.size();
            unordered_set<vector<int>> dict;
            vector<vector<int>> result;
            if(_size==0)  return result;
            sort(nums.begin(), nums.end());
            
            int count=power(2, nums.size());
            for(int i=0; i<count; i++){
                vector<int> temp;
                for(int j=0; j<nums.size(); j++){
                    (i>>j)&1 ? temp.push_back(nums[j]) : {};
                }
                if(dict.find(temp)!=dict.end()){
                    continue;
                }
                dict.insert(temp);
                result.push_back(temp);
            }
            return result;
        }
    };

  • 0

    i got the advice from others that the unordered_set<> does not support vector<int> to be the key default


  • 0
    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<int> cur;
            vector<vector<int>> result;
            result.push_back(cur);
            help(result, cur, nums, 0);
            return result;
        }
        /*** consider to put_back the 1-size-subset   2-size-subset  3-size-subset ***/
        void help(vector<vector<int>> &result, vector<int>& cur, vector<int> &nums, int pos){
            for(int i=pos; i<nums.size(); i++){
                /*** just as the previous solution ***/
                /*** we just consider all the subset started with nums[i] ***/
                cout<<pos<<":"<<i<<endl;
                if(i>pos && nums[i]==nums[i-1])  continue;
                cur.push_back(nums[i]);
                result.push_back(cur);
                help(result, cur, nums, i+1);
                cur.pop_back();
            }
        }
    };
    

    **

     This solution is consider to push_back all the sub set starting with different elements value !! 
    

    **


  • 0

    we can change the condition to

    if(i==pos || nuts[i]!=nums[i-1]) it is the same


  • 0
    This post is deleted!

  • 0

    level-by-level BFS solution

    Code:

      class Solution {
        public:
            vector<vector<int>> subsetsWithDup(vector<int>& nums) {
                vector<vector<int>> result={{}};
                sort(nums.begin(), nums.end());
                /*** add the subset level by level ***/
                int i=0;
                while(i<nums.size()){
                    /*** count all the duplicate cases ***/
                    int count=0;
                    while(count+i<nums.size() && nums[count+i]==nums[i]) count++;
                    int level=result.size();
                    /*** for every previous elem, add [0-count]-duplicates ***/
                    for(int k=0; k<level; k++){
                        vector<int> temp=result[k];
                        for(int j=0; j<count; j++){
                            temp.push_back(nums[i]);
                            result.push_back(temp);
                        }
                    }
                    i+=count;
                }
                return result;
            }
        };

  • 0
    2

    In my first implementation I used to add a end checking parameter to check whether to add the path to the result ...... So you know I only get the some results and miss many cases !

    So here is my implementation ...

    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            int size_nums = nums.size();
            vector<vector<int>> result{};
            vector<int> path;
            sort(nums.begin(), nums.end());
            help(nums, path, result, 0);
            return result;
        }
        
        void help(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, int pos) {
            result.push_back(path);
            for(int i = pos; i < nums.size(); i++) {
                if(i > pos && nums[i] == nums[i-1])  continue;
                path.push_back(nums[i]);
                help(nums, path, result, i + 1);
                path.pop_back();
            }
        }
    };

Log in to reply
 

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