Share three methods, collecting from previous discussing(C++)


  • 1
    E
    //bitmap 12ms
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        n = nums.size();
        vector<vector<int>> res(1, vector<int>());
        if (n == 0) return res;
        sort(nums.begin(), nums.end());
        int mask = 0, total = pow(2, n), tmpi, tmpj, lastnum;
        bool dp;
        for (int i = 1; i < total; i++) {
            dp = false;
            vector<int> tmp;
            lastnum = -1;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    //check if duplicate
                    tmpi = nums[j];
                    if (nums[j] == lastnum) {
                        tmpj = j - 1;
                        while (tmpj >= 0 && nums[tmpj] == lastnum) {
                            if (!(i & (1 << tmpj))) {
                                dp = true;
                                break;
                            }
                            tmpj--;
                        }
                    }
                    if (dp) break;
                    tmp.push_back(tmpi);
                }
                lastnum = nums[j];
            }
            if (dp) continue;
            res.push_back(tmp);
        }
        
        return res;
    }
    
    //recursive 8ms
    vector<vector<int>> res;
    int n;
    void generate(vector<int>& num, vector<int>& tmp, int k) {
        res.push_back(tmp);
        for (int i = k; i < n; i++) {
            tmp.push_back(num[i]);
            generate(num, tmp, i + 1);
            tmp.pop_back();
            while (i < n - 1 && num[i] == num[i + 1]) {
                i++;
            }
        }
    }
    
    vector<vector<int>> subsetsWithDup3(vector<int>& nums) {
        n = nums.size();
        vector<int> tmp;
        sort(nums.begin(), nums.end());
        generate(nums, tmp, 0);
        return res;
    }
    
    //another recursive 12ms
        vector<vector<int>> subsetsWithDup2(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> res(1, vector<int>());
            if (n == 0) return res;
            sort(nums.begin(), nums.end());
            int m, tmpi;
            for (int i = 0; i < n; i++) {
                tmpi = 1;
                while (i - tmpi >= 0 && nums[i - tmpi] == nums[i]) tmpi++;
                tmpi--;
                m = res.size();
                for (int j = 0; j < m; j++) {
                    if (tmpi > 0 && (res[j].empty() || res[j].size() < tmpi || res[j][res[j].size() - tmpi] != nums[i])) continue;
                    vector<int> tmp = res[j];
                    tmp.push_back(nums[i]);
                    res.push_back(tmp);
                }
            }
            return res;
        }

Log in to reply
 

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