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

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

  12. Thank you a lot for providing individuals with an extremely marvellous opportunity to discover important secrets from here. It’s usually so great plus stuffed with a great time for me and my office colleagues to search your site more than thrice every week to see the new stuff you have. Of course, I’m at all times fascinated considering the powerful ideas you give. Selected 4 tips in this article are unequivocally the simplest we’ve ever had.

  13. I must point out my admiration for your generosity for persons who must have guidance on this particular issue. Your special commitment to passing the solution around has been wonderfully beneficial and have continually empowered some individuals like me to realize their goals. Your new interesting suggestions means a whole lot to me and even further to my office workers. Warm regards; from everyone of us.

  14. I precisely wished to thank you very much once more. I’m not certain the things that I would’ve worked on in the absence of the entire secrets provided by you regarding this subject matter. It absolutely was a very frightful circumstance in my view, nevertheless taking note of a skilled manner you dealt with that made me to weep with happiness. Now i am grateful for the service and in addition trust you realize what an amazing job you happen to be providing instructing people today through the use of your site. Probably you’ve never got to know all of us.

  15. Needed to post you the little word to be able to give many thanks the moment again regarding the fantastic solutions you’ve discussed on this site. It’s simply seriously generous of people like you to present publicly exactly what many people could possibly have distributed as an e book to make some money for their own end, especially given that you could possibly have tried it if you ever decided. These concepts additionally worked as the good way to fully grasp that some people have the same dreams just like my very own to figure out more and more around this condition. I’m certain there are lots of more fun situations up front for many who read through your site.

  16. Thanks a lot for giving everyone a very terrific possiblity to read critical reviews from here. It really is very amazing plus full of a great time for me and my office acquaintances to search the blog nearly 3 times weekly to see the newest items you have got. Of course, I’m just usually happy with the fabulous hints you give. Some 2 areas in this article are undoubtedly the simplest I’ve had.

  17. I would like to point out my gratitude for your kind-heartedness giving support to those who really want help on in this matter. Your very own commitment to getting the solution around came to be quite interesting and have usually helped most people just like me to attain their dreams. This invaluable guide can mean a whole lot a person like me and still more to my office colleagues. Best wishes; from everyone of us.

  18. I have to voice my admiration for your kind-heartedness in support of folks that really need guidance on this area of interest. Your very own dedication to passing the solution around was extremely interesting and has usually permitted guys and women like me to achieve their pursuits. Your amazing warm and friendly facts indicates much to me and far more to my colleagues. Regards; from all of us.

  19. I precisely needed to thank you very much once again. I am not sure the things I would have sorted out without the type of suggestions shown by you regarding such subject. It seemed to be a real fearsome scenario in my circumstances, however , witnessing your specialized tactic you resolved that took me to cry for happiness. I’m thankful for this advice and then hope that you recognize what a powerful job that you are undertaking instructing the mediocre ones using a web site. I’m certain you’ve never encountered all of us.

  20. My spouse and i ended up being so fulfilled when Michael managed to conclude his research through the ideas he obtained through the web site. It’s not at all simplistic to simply choose to be offering helpful tips that many some people may have been selling. And we also realize we have got the writer to be grateful to because of that. The entire illustrations you have made, the straightforward blog menu, the friendships you will assist to foster – it’s everything incredible, and it’s really assisting our son in addition to the family recognize that that subject matter is interesting, and that’s really fundamental. Thank you for everything!

  21. }{Always remember that there are tons of different options available to you when looking for hair accessories. The sky is really the limit here, and you can choose from different braids and headbands, bows and ribbons, clips and curlers, and much, much more. Your wardrobe should include several hair accessories. A simple ponytail holder goes great with an athletic suit. So before you go out, make sure you’re carrying a few accessories with you.

Leave a Reply

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