[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;
};

14 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.

  8. I simply wished to thank you so much yet again. I am not sure the things I might have created in the absence of the entire aspects shown by you directly on my field. It was a traumatic condition in my view, however , taking a look at the professional fashion you dealt with it made me to weep for happiness. Now i’m happier for the information as well as trust you are aware of an amazing job you were accomplishing educating people all through a web site. Most probably you’ve never got to know all of us.

  9. Needed to write you that bit of remark to give many thanks yet again for those superb basics you have contributed here. It is simply pretty open-handed of you to give easily what many of us could possibly have advertised for an e-book to help make some money for their own end, precisely considering that you might well have done it if you wanted. Those ideas in addition served to provide a easy way to realize that some people have a similar interest just as my own to realize a little more on the subject of this condition. I believe there are some more pleasurable times up front for people who look over your website.

  10. Thanks a lot for giving everyone an extraordinarily wonderful opportunity to read from here. It is often so awesome and packed with a great time for me personally and my office co-workers to visit your site not less than three times every week to find out the latest items you will have. And of course, I’m also actually contented with your striking creative concepts you serve. Selected two ideas in this post are ultimately the most suitable we’ve had.

  11. I want to point out my affection for your kind-heartedness for people that actually need assistance with in this niche. Your special dedication to getting the solution across appeared to be surprisingly significant and have truly allowed many people like me to achieve their dreams. Your entire useful useful information means a great deal a person like me and substantially more to my office colleagues. Best wishes; from everyone of us.

Leave a Reply

Your email address will not be published.