LC 90 Subset II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

Avoid duplicates

In subset 1, the input are unique and we just build a tree where each level i has all combination with length i.

But using that method will give us duplicate. For example input [1,2,2], the len 1 subsets will contain [1], [2], [2]. But we still want each node in the same level to be unique.

To avoid duplicates, at each level, we only append and recur on unique characters.
We achieve this by sorting the inputs, then the duplicates will be next to each other and we just skip the duplicates through checking prev.

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        if(nums.empty()) return res;
        vector<int> curSol;
        int prev = *max_element(nums.begin(), nums.end());
        prev ++;
        subsetRecur(nums, 0, curSol, res, prev);
        return res;
    }

    void subsetRecur(vector<int>& input, int start, vector<int> curSol, vector<vector<int>> & res, int prev){
        if(start == input.size() + 1){ 

        }
        else{
            int localPrev = prev;
            res.push_back(curSol);
            for(int i = start; i < input.size(); i ++){
                if(localPrev != input[i]){
                curSol.push_back(input[i]);
                subsetRecur(input, i + 1, curSol, res, prev);
                curSol.pop_back();    
                }
                localPrev = input[i];

            }    
        }
    }
};

Potential bug

I used max(vector) + 1 as the prev so the first element will always be unique and added to the tree. But what if max(vector) == MAXINT?

We can just automatically append the nums[start] in the result automatically

if(i == start || input[i] != input[i - 1]){

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax