90. Subsets II

Description

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

Solutions

Solution 1: Sorting + DFS

Thinking

The first idea is the same DFS as Subsets: take or skip each index. Correct, but duplicates make \([1, 2]\) appear twice. \(n \le 10\) is small, yet the solution set must be unique.

The bottleneck is treating equal values at different indices as distinct choices. Sort so equals sit together; skip the same value on the “not take” branch so each multiset is generated once.

After sorting, DFS: take \(i\), then on the skip path jump over every later equal \(\textit{nums}[i]\). How many copies we take is decided by recursion depth, never as two identical subsets side by side.

We can first sort the array \(\textit{nums}\) to facilitate deduplication.

Then, we design a function \(\textit{dfs}(i)\), which represents the current search for subsets starting from the \(i\)-th element. The execution logic of the function \(\textit{dfs}(i)\) is as follows:

If \(i \geq n\), it means all elements have been searched, add the current subset to the answer array, and end the recursion.

If \(i < n\), add the \(i\)-th element to the subset, execute \(\textit{dfs}(i + 1)\), then remove the \(i\)-th element from the subset. Next, we check if the \(i\)-th element is the same as the next element. If they are the same, skip the element in a loop until we find the first element different from the \(i\)-th element, then execute \(\textit{dfs}(i + 1)\).

Finally, we only need to call \(\textit{dfs}(0)\) and return the answer array.

The time complexity is \(O(n \times 2^n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScriptRustJavaScriptC#

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == len(nums):
                ans.append(t[:])
                return
            t.append(nums[i])
            dfs(i + 1)
            x = t.pop()
            while i + 1 < len(nums) and nums[i + 1] == x:
                i += 1
            dfs(i + 1)

        nums.sort()
        ans = []
        t = []
        dfs(0)
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i >= nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        t.add(nums[i]);
        dfs(i + 1);
        int x = t.remove(t.size() - 1);
        while (i + 1 < nums.length && nums[i + 1] == x) {
            ++i;
        }
        dfs(i + 1);
    }
}

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        vector<int> t;
        int n = nums.size();
        auto dfs = [&](this auto&& dfs, int i) {
            if (i >= n) {
                ans.push_back(t);
                return;
            }
            t.push_back(nums[i]);
            dfs(i + 1);
            t.pop_back();
            while (i + 1 < n && nums[i + 1] == nums[i]) {
                ++i;
            }
            dfs(i + 1);
        };
        dfs(0);
        return ans;
    }
};

func subsetsWithDup(nums []int) (ans [][]int) {
    slices.Sort(nums)
    n := len(nums)
    t := []int{}
    var dfs func(int)
    dfs = func(i int) {
        if i >= n {
            ans = append(ans, slices.Clone(t))
            return
        }
        t = append(t, nums[i])
        dfs(i + 1)
        t = t[:len(t)-1]
        for i+1 < n && nums[i+1] == nums[i] {
            i++
        }
        dfs(i + 1)
    }
    dfs(0)
    return
}

function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const t: number[] = [];
    const ans: number[][] = [];
    const dfs = (i: number): void => {
        if (i >= n) {
            ans.push([...t]);
            return;
        }
        t.push(nums[i]);
        dfs(i + 1);
        t.pop();
        while (i + 1 < n && nums[i] === nums[i + 1]) {
            i++;
        }
        dfs(i + 1);
    };
    dfs(0);
    return ans;
}

impl Solution {
    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums;
        nums.sort();
        let mut ans = Vec::new();
        let mut t = Vec::new();

        fn dfs(i: usize, nums: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            if i >= nums.len() {
                ans.push(t.clone());
                return;
            }
            t.push(nums[i]);
            dfs(i + 1, nums, t, ans);
            t.pop();
            let mut i = i;
            while i + 1 < nums.len() && nums[i + 1] == nums[i] {
                i += 1;
            }
            dfs(i + 1, nums, t, ans);
        }

        dfs(0, &nums, &mut t, &mut ans);
        ans
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const t = [];
    const ans = [];
    const dfs = i => {
        if (i >= n) {
            ans.push([...t]);
            return;
        }
        t.push(nums[i]);
        dfs(i + 1);
        t.pop();
        while (i + 1 < n && nums[i] === nums[i + 1]) {
            i++;
        }
        dfs(i + 1);
    };
    dfs(0);
    return ans;
};

public class Solution {
    private IList<IList<int>> ans = new List<IList<int>>();
    private IList<int> t = new List<int>();
    private int[] nums;

    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        this.nums = nums;
        Dfs(0);
        return ans;
    }

    private void Dfs(int i) {
        if (i >= nums.Length) {
            ans.Add(new List<int>(t));
            return;
        }
        t.Add(nums[i]);
        Dfs(i + 1);
        t.RemoveAt(t.Count - 1);
        while (i + 1 < nums.Length && nums[i + 1] == nums[i]) {
            ++i;
        }
        Dfs(i + 1);
    }
}

Solution 2: Sorting + Binary Enumeration

Thinking

Solution 1 already deduplicates, but recursion pays a stack and the skip logic is easy to get wrong. \(n \le 10\), so we can enumerate all \(2^n\) masks.

What it lacks is “take or skip” as bits. Bit \(i\) of \(\textit{mask}\) means taking \(\textit{nums}[i]\); taking \(i\) without \(i - 1\) when the values are equal skips an earlier copy — a duplicate, drop it. Same asymptotics, one loop.

Similar to Solution 1, we first sort the array \(\textit{nums}\) to facilitate deduplication.

Next, we enumerate a binary number \(\textit{mask}\) in the range \([0, 2^n)\), where the binary representation of \(\textit{mask}\) is an \(n\)-bit bit string. If the \(i\)-th bit of \(\textit{mask}\) is \(1\), it means selecting \(\textit{nums}[i]\), and \(0\) means not selecting \(\textit{nums}[i]\). Note that if the \((i - 1)\)-th bit of \(\textit{mask}\) is \(0\) and \(\textit{nums}[i] = \textit{nums}[i - 1]\), it means that the \(i\)-th element is the same as the \((i - 1)\)-th element in the current enumeration scheme. To avoid duplication, we skip this case. Otherwise, we add the subset corresponding to \(\textit{mask}\) to the answer array.

After the enumeration, we return the answer array.