Another method to generate subsets iteratively. C++ ~48ms


  • 0
    J

    My algorithm is adapted from an iterative algorithm of the Subset puzzle.

    Although this is not the best algorithm for this puzzle, compare to another one, I still want to share it.

    Instead of taking one number as a basic unit, I use one set of identical numbers as the basic unit. When I see 1,2,2, I think about [1],[2],[2,2].

    Every time, I insert a few identical numbers into the old subsets. If the last number of the subset is identical to the current numbers, just skip, so as to avoid duplicates.

    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int> &S) {
            vector<int> set = S;
            sort(set.begin(), set.end());  // now the numbers are in ascending order
            vector<int> counts(set.size(), 1);
            vector<vector<int>> superset = {{}};
            for (int i = 0; i < set.size(); i++) {
                if (i > 0 && set[i-1] == set[i]) {
                    counts[i] = counts[i-1] + 1;  // the nth-identical number
                }
                int size = superset.size();
                for (int j = 0; j < size; j++) {
                    if (!superset[j].empty() && superset[j].back() == set[i]) {
                        continue;  // [x], [x,x], ..., [x,x,...] conflict with each other
                    }
                    vector<int> subset = superset[j];
                    //subset.reserve(subset.size() + counts[i]);
                    for (int k = 0; k < counts[i]; k++) {
                        subset.push_back(set[i]);
                    }
                    superset.push_back(subset);
                }
            }
            return superset;
        }
    };

  • 0
    Z
    This post is deleted!

  • 0
    Z

    if (!superset[j].empty() && superset[j].back() == set[i]) {
    continue; // [x], [x,x], ..., [x,x,...] conflict with each other
    }
    I think you can use break instead of continue here, because the last elements of the rest subsets are the same and equal to set[i].


  • 0
    J

    Oh, yes. You're right!


Log in to reply
 

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