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