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

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

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.