C++ solutions


  • 0
    A
    1. iterative
    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans = {{}};
            int i = 0;
            while (i < nums.size()) {
                int count = 1;
                while (i + count < nums.size() && nums[i] == nums[i + count])
                    ++count;
                
                int n = ans.size();
                for (int j = 0; j < n; ++j) {
                    vector<int> s = ans[j];
                    for (int k = 0; k < count; ++k) {
                        s.push_back(nums[i]);
                        ans.push_back(s);
                    }
                }
                
                i += count;
            }
            return ans;
        }
    };
    
    1. dfs and backtracking. based on Subsets but skip duplicates when not using current number
    class Solution {
    public:
        void helper(vector<vector<int>> &ans, vector<int> &s, vector<int> &nums, int i) {
            if (i == nums.size()) {
                ans.push_back(s);
                return;
            }
            
            s.push_back(nums[i]);
            helper(ans, s, nums, i + 1);
            s.pop_back();
            
            while (i + 1 < nums.size() && nums[i] == nums[i + 1])
                ++i;
            helper(ans, s, nums, i + 1);
        }
    
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans;
            vector<int> s;
            helper(ans, s, nums, 0);
            return ans;
        }
    };
    

Log in to reply
 

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