{"id":11474,"date":"2022-06-12T19:56:48","date_gmt":"2022-06-12T19:56:48","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11474"},"modified":"2022-06-12T19:56:48","modified_gmt":"2022-06-12T19:56:48","slug":"programming-problem-subsets-ii","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11474","title":{"rendered":"[Programming Problem] Subsets II"},"content":{"rendered":"<p>Given an integer array nums that may contain duplicates, return all possible subsets (the power set).<br \/>\nThe solution set must not contain duplicate subsets. Return the solution in any order.<\/p>\n<p>Example 1:<\/p>\n<p>Input: nums = [1,2,2]<br \/>\nOutput: [[],[1],[1,2],[1,2,2],[2],[2,2]]<\/p>\n<p>Example 2:<\/p>\n<p>Input: nums = [0]<br \/>\nOutput: [[],[0]]<\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/subsets-ii\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<p>Let&#8217;s use backtracking to create our subsets. We&#8217;ll use a Set to know if the subset if already in our return array (key is simply concatenated version of the array).<\/p>\n<p>[1, 2, 1]<\/p>\n<p>Index 3: []<br \/>\nIndex 2: []             [1]<br \/>\nIndex 1: [][1]          [2][2,1]<br \/>\nIndex 0: [][1][2][2,1]  <del datetime=\"2022-06-12T19:33:37+00:00\">[1]<\/del>[1,1][1,2][1,2,1]<\/p>\n<p>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.<\/p>\n<p>[1, 1, 2]<\/p>\n<p>Index 3: []<br \/>\nIndex 2: []             [2]<br \/>\nIndex 1: [][2]          [1][1,2]<br \/>\nIndex 0: [][2][1][1,2]  <del datetime=\"2022-06-12T19:33:37+00:00\">[1][1,2]<\/del>[1,1][1,1,2]<\/p>\n<pre lang=\"javascript\">\r\n\/**\r\n * @param {number[]} nums\r\n * @return {number[][]}\r\n *\/\r\nvar subsetsWithDup = function(nums) {\r\n    return subsetsWithDupCalc(0, nums.sort(), new Set());\r\n};\r\n\r\nvar subsetsWithDupCalc = function(i, nums, retSet) {\r\n    if (i === nums.length) return [[]];\r\n    \r\n    let ret = subsetsWithDupCalc(i+1, nums, retSet);\r\n    let newRet = [...ret];\r\n    ret.forEach((arr) => {\r\n        let curr = [nums[i], ...arr];\r\n        if (!retSet.has(curr.join(''))) {\r\n            newRet.push(curr);\r\n            retSet.add(curr.join(''));\r\n        }\r\n    });\r\n    \r\n    return newRet;\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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&#8217;s use backtracking to create our subsets. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11474","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11474","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11474"}],"version-history":[{"count":4,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11474\/revisions"}],"predecessor-version":[{"id":11478,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11474\/revisions\/11478"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11474"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11474"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11474"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}