LeetCode 90. Subsets II

Question

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

Source: https://leetcode.com/problems/subsets-ii/

Solution

Set is a kind of combination without constraint of length.

The given array may contain duplicates. So we pre-sort nums, which enables us to conveninently skip duplicate elements on DFS layers.

private void dfs(int[] sortedNums, int startPos, LinkedList<Integer> current, List<List<Integer>> result) {
    if (startPos == sortedNums.length) {
        List<Integer> copy = new ArrayList<>(current);
        result.add(copy);
        return;
    }
    // do not add any more elements
    // regarded as a subset
    dfs(sortedNums, sortedNums.length, current, result);

    for (int i = startPos; i < sortedNums.length; i++) {
        int n = sortedNums[i];
        // skip used elements in this layer
        if (i != startPos && sortedNums[i] == sortedNums[i - 1]) {
            continue;
        }
        // backtrace
        current.addLast(n);
        dfs(sortedNums, i + 1, current, result);
        current.removeLast();
    }
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> subsets = new ArrayList<>();
    LinkedList<Integer> subset = new LinkedList<>();
    Arrays.sort(nums);
    dfs(nums, 0, subset, subsets);
    return subsets;
}