Subsets II

Problem

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]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const res = [];
    backtrack(res, [], nums.sort(), 0);
    return res;
};

var backtrack = function(res, path, nums, start) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
        if (i > start && nums[i] === nums[i - 1]) { // duplicate
            continue;
        }
        path.push(nums[i]);
        backtrack(res, path, nums, i + 1);
        path.pop();
    }
};

We will implement a backtracking (DFS) solution. The logic is the same as Subsets, except we must add an extra condition to take care of duplicate values. More specifically, we sort nums and only include duplicate elements in path if it is the first time encountering said value at said index taking into account all calls made to backtrack so far (ie. i == start).

Problem​

Solution​

Problem

Solution