Subsets II

LeetCode 90 | Difficulty: Medium

Medium

Problem 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`

Topics: Array, Backtracking, Bit Manipulation

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 573 ms)

Metric	Value
Runtime	573 ms
Memory	N/A
Date	2018-01-26

Solution

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
       Array.Sort(nums);
    List<IList<int>> dp = new List<IList<int>>();
    for (int i = 0; i <= nums.Length; i++)
    {
        SubsetsBackTrack2(dp, new List<int>(), 0, nums, i);
    }

    return dp;
}

public void SubsetsBackTrack2(List<IList<int>> combinations, List<int> templist, int start, int[] nums, int k)
{
    if (k == 0)
    {
        combinations.Add(templist.ToList());
    }
    if (nums.Length - start + 1 >= k)
        for (int i = start; i < nums.Length; i++)
        {
            if (i == start || nums[i] != nums[i - 1])
            {
                templist.Add(nums[i]);
                SubsetsBackTrack2(combinations, templist, i + 1, nums, k - 1);
                templist.RemoveAt(templist.Count - 1);

            }
        }
}

}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.