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 allows us to easily identify and handle duplicate numbers, preventing duplicate subsets.

2. Backtracking: Use a recursive backtracking approach to generate subsets. For each number in the sorted array:

   • Decide whether to include the number in the current subset or not.
   • If included, add it to the current subset and recursively explore further.
   • If not included, move to the next number.

3. Skip duplicates: When encountering a duplicate number, skip it if it's already been considered in the previous recursion level (to prevent duplicate subsets). This is achieved by checking if the current number is the same as the previous number, and if it is, only process it if the skip boolean is false. This ensures we don't skip the first occurrence of a duplicate.

4. Store Results: Store the generated subsets in a List<List<Integer>>.

Explanation

The backtracking approach systematically explores all possible combinations of including or excluding each element. Sorting ensures that duplicate numbers are processed only once, thus preventing duplicate subsets from being generated. The skip boolean elegantly handles the duplicate skipping logic, ensuring that only unique combinations are considered.

Code

import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Sort to handle duplicates
        backtrack(nums, 0, new ArrayList<>(), result, false); //Initiate backtracking
        return result;
    }

    private void backtrack(int[] nums, int index, List<Integer> currentSubset, List<List<Integer>> result, boolean skip) {
        result.add(new ArrayList<>(currentSubset)); // Add current subset to results

        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1] && !skip) { //Skip duplicates if not first occurrence.
                backtrack(nums, i + 1, currentSubset, result, true); // recursive call with skip set to true.
            }else{
                currentSubset.add(nums[i]);
                backtrack(nums, i + 1, currentSubset, result, false); // recursive call including current element
                currentSubset.remove(currentSubset.size() - 1); // backtrack: remove the last element for next iteration.
                }

        }
    }
}

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 perform O(N) operations (e.g., copying the subset).
• Space Complexity: O(N * 2^N) in the worst case, to store all possible subsets. The recursion depth is also O(N).