Subsets II medium

Problem Statement

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,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0] Output: [[],[0]]

Steps

1. Sort the input array: Sorting the input array allows us to easily handle duplicates and avoid generating duplicate subsets.

2. Backtracking Algorithm: We use a backtracking algorithm to explore all possible subsets. The algorithm recursively builds subsets by either including or excluding the current element.

3. Handling Duplicates: Because the input array might contain duplicates, we need to add a check to avoid creating duplicate subsets. We only consider adding an element if it's different from the previous element or if it's the first element considered in the current recursive call.

4. Store and Return Results: We store all generated subsets in a result array and return it at the end.

Explanation

The backtracking algorithm works by iterating through the sorted input array. For each element, it has two choices: include the element in the current subset or exclude it. It recursively explores both possibilities. The base case of the recursion is when we've processed all elements of the input array; at that point, we add the current subset to the result array.

The key to handling duplicates is the condition i > 0 && nums[i] == nums[i - 1] && !include. This prevents adding an element if it's a duplicate of the previous element and if we are not currently including that element in the subset. This avoids generating duplicate subsets like [1,2] and [2,1] (after sorting the input).

Code

function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a, b) => a - b); // Sort the input array
    const result: number[][] = [];
    const subset: number[] = [];

    function backtrack(index: number) {
        result.push([...subset]); // Add a copy of the current subset

        for (let i = index; i < nums.length; i++) {
            //Skip duplicate elements if not including them
            if (i > 0 && nums[i] == nums[i - 1] && !subset.includes(nums[i])) {
                continue;
            }
            subset.push(nums[i]);
            backtrack(i + 1); //Recursive call including the current element
            subset.pop(); //Backtrack -remove the element
        }
    }

    backtrack(0);
    return result;
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the input array. This is because there are 2^N possible subsets, and for each subset, we might need to copy its elements (taking O(N) time).

• Space Complexity: O(N * 2^N) in the worst case, due to the space used to store the result (all possible subsets). The recursion stack also takes up O(N) space in the worst case.