[Programming Problem] Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

[Problem Link]

Let’s use backtracking to create our subsets. We’ll use a Set to know if the subset if already in our return array (key is simply concatenated version of the array).

[1, 2, 1]

Index 3: []
Index 2: [] [1]
Index 1: [][1] [2][2,1]
Index 0: [][1][2][2,1] [1][1,1][1,2][1,2,1]

Notice what happened here. The same subset [1, 2] and [2, 1] get counted as different subsets. To avoid this we run the same algorithm on the sorted version of the input.

[1, 1, 2]

Index 3: []
Index 2: [] [2]
Index 1: [][2] [1][1,2]
Index 0: [][2][1][1,2] [1][1,2][1,1][1,1,2]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    return subsetsWithDupCalc(0, nums.sort(), new Set());
};
 
var subsetsWithDupCalc = function(i, nums, retSet) {
    if (i === nums.length) return [[]];
 
    let ret = subsetsWithDupCalc(i+1, nums, retSet);
    let newRet = [...ret];
    ret.forEach((arr) => {
        let curr = [nums[i], ...arr];
        if (!retSet.has(curr.join(''))) {
            newRet.push(curr);
            retSet.add(curr.join(''));
        }
    });
 
    return newRet;
};

10 thoughts on “[Programming Problem] Subsets II

  1. I precisely desired to thank you so much again. I do not know the things I would have done without those techniques provided by you directly on this area. It was actually an absolute hard dilemma in my opinion, however , spending time with your expert strategy you dealt with it forced me to leap for fulfillment. I’m thankful for this support as well as trust you really know what a great job you are always getting into training some other people thru a web site. I know that you’ve never got to know any of us.

  2. I’m just commenting to let you be aware of of the impressive encounter my cousin’s princess went through viewing the blog. She came to find plenty of things, most notably what it’s like to have an amazing teaching spirit to let certain people with no trouble know some very confusing topics. You really exceeded my expectations. I appreciate you for showing such necessary, safe, edifying and as well as fun tips about that topic to Lizeth.

  3. I wanted to compose you this very small word to thank you again with your great strategies you’ve discussed above. It’s really seriously open-handed with you to present extensively precisely what some people would’ve distributed for an ebook to make some cash for their own end, especially since you might have done it if you ever desired. These pointers in addition served like the easy way to recognize that the rest have the same keenness the same as my personal own to know good deal more on the topic of this matter. I am certain there are numerous more fun occasions ahead for people who read carefully your site.

  4. I and also my guys appeared to be viewing the best guides from your site and so the sudden I had an awful feeling I had not thanked the blog owner for them. All the ladies appeared to be so glad to read all of them and already have honestly been taking pleasure in them. Many thanks for indeed being indeed kind and then for using these kinds of useful subject matter millions of individuals are really desirous to be aware of. My personal sincere apologies for not expressing appreciation to you earlier.

  5. I have to point out my love for your kind-heartedness supporting men who should have assistance with this particular study. Your real dedication to passing the message all over came to be pretty powerful and has without exception empowered workers much like me to realize their targets. This informative facts denotes so much to me and further more to my office colleagues. Regards; from everyone of us.

  6. I want to get across my affection for your generosity in support of men who require help with your concern. Your very own dedication to passing the solution along has been pretty significant and has specifically empowered somebody like me to reach their ambitions. Your personal informative instruction denotes so much to me and even further to my office colleagues. Thank you; from each one of us.

  7. I wanted to put you that bit of remark to be able to thank you very much yet again about the striking tactics you’ve featured on this page. It is incredibly generous with people like you to allow unreservedly all that many of us could possibly have supplied as an e book in making some dough for themselves, and in particular given that you might well have tried it in the event you wanted. These basics in addition worked to be the great way to be aware that someone else have the identical zeal really like my personal own to understand whole lot more when considering this matter. I think there are many more pleasant situations ahead for those who find out your website.

Leave a Reply

Your email address will not be published.