fastest 8ms C++ iterative solution, beats 80%, with detailed explaination


  • 3
    T

    The idea is pretty simple, first we consider the case of Subset I where there is no duplicates in nums, and we can easily figure out a solution like this one:
    https://discuss.leetcode.com/topic/11373/c-8ms-simple-iterative-solution
    The key point is that every time we take all vectors from sol and append a new number to them.

    Now when there are duplicates, we simply need to add one line of code to adapt the previous solution to our need. There are two situations:

    1. when nums[i] != nums[i+1], then it is the same as before, we copy all vectors in sol and append a new number[i+1] to them
    2. when nums[i] == nums[i+1], now we dont want to redo what has been done in nums[i], so we need to know what new vectors are added in nums[i] step and we only want to append nums[i+1] to them.
      In the following code, start is the starting position of new vectors added in nums[i] step.
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> sol(1);
            int start = 0;
            for (int i = 0; i < nums.size(); i++){
                int n = sol.size();
                for (int j = start; j < n; j++){
                    sol.push_back(sol[j]);
                    sol.back().push_back(nums[i]);
                }
                // start is the beginning of new vectors add by nums[i]
                if (i < nums.size()-1 && nums[i]==nums[i+1]) start = sol.size()-(n-start);
                else start = 0;
            }
            return sol;
        }
    

  • 2
    H

    Nice solution, a minor improvement as below:

    if (i < nums.size()-1 && nums[i]==nums[i+1]) start = n;
    

Log in to reply
 

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