algoadvance

Leetcode 90. Subsets II

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:

• Input: nums = [1,2,2]
• Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Clarifying Questions

1. Can the input array be empty?
   • Yes, the input array can be empty, in which case the output should be a list containing just the empty subset: [[]].
2. Should the output subsets be in any specific order?
   • No specific order is required for the output subsets, as long as all unique subsets are included.

Strategy

1. Sort the Input:
   • Sorting the input array helps in handling duplicates easily.
2. Backtracking:
   • Use a backtracking approach to generate subsets.
   • Skip over duplicate elements by checking the current element against the previous one.
   • Use a helper function to build subsets recursively.
   • Start with an empty list and add elements, while ensuring that duplicates are not considered in the same depth level.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
        result.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            // Skip duplicate elements
            if (i > start && nums[i] == nums[i - 1]) continue; 
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        SubsetsII solution = new SubsetsII();
        int[] nums = {1, 2, 2};
        System.out.println(solution.subsetsWithDup(nums));
    }
}

Time Complexity

• Sorting: O(n log n), where n is the number of elements in nums.
• Backtracking: Each element can either be included or not included, generating 2^n subsets. However, due to duplicates, this is reduced, but the worst case is still O(2^n).
• Total: O(n log n + 2^n).

This ensures we generate all possible subsets while effectively handling duplicates.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?