С++ iterative with O(1) check for duplicates


  • 0

    Firstly, we sort our nums, then to avoid duplicates:

    1. If nums[i-1] != nums[i] we append to every vector with last element less or equal than nums[i]
    2. If nums[i-streak-1]==..==nums[i-1] == nums[i] then we have only one vector with all nums[i] "streak+1" times and we want to add nums[i] only to this one

    Example:
    nums[i-3] == nums[i-2] == nums[i-1] == nums[i] == 2
    ...
    res[i1] = 1, 2 <- skip
    res[i2] = 1, 2, 2 <- skip
    res[i2] = 1, 2, 2, 2 <- copy and append 2

    So we keep track of the current length ("streak" variable + 1) of the sequence and append nums[i] only to the vector that contains all of the previous nums equal to nums[i]

      vector<vector<int>> subsetsWithDup(vector<int>& nums)
      {
          vector<vector<int>> res {{}};
    
          sort(nums.begin(), nums.end());
          int streak = 0;
      
          for (int i = 0; i < nums.size(); ++i)
          {
              if (i && nums[i-1] == nums[i]) ++streak; else streak = 0;
     
              for (int j = res.size(); j--; )
               {
                  auto r = res[j];
                  if (r.size() && r[r.size()-1] > nums[i]) continue;
                  if (streak && ( r.size() < streak || r[r.size()-streak] != nums[i])) continue; // the one with all of the previous has r[r.size()-streak] the same as nums[i]
      
                  vector<int> ri(r.begin(), r.end());
                  ri.push_back(nums[i]);
                  res.push_back(ri);
              }
          }
      
          return res;
      }

Log in to reply
 

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