Subsets II

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Backtracking, Recursion, Arrays, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What is a subset (and what is the power set)?

  • A: A subset is any selection of elements from nums, including the empty selection and the full list. The power set is the collection of all such subsets.

• Q: The input may contain duplicate values. How does that affect the output?

  • A: Duplicate values can produce identical subsets through different choices (picking the first 2 vs. the second 2 in [1, 2, 2]). The solution set must not contain duplicate subsets, so we need a way to generate each distinct subset exactly once.

• Q: Does the order of subsets in the output matter?

  • A: No, the subsets can be returned in any order, as long as every distinct subset appears exactly once.

HAPPY CASE
Input: nums = [1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Explanation: [1, 2] appears only once even though it could be formed with either of the two 2s. All 6 distinct subsets are returned.

EDGE CASE
Input: nums = []
Output: [[]]
Explanation: The power set of an empty list contains exactly one subset: the empty subset.

Input: nums = [2, 2, 2]
Output: [[], [2], [2, 2], [2, 2, 2]]
Explanation: Even though there are 8 ways to choose elements, only 4 distinct subsets exist when every element is the same.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating Combinations/Subsets, we can consider the following approaches:

• Backtracking: Build subsets incrementally by choosing or skipping each element, recording every partial selection as a valid subset. This is the standard pattern for power-set problems.
• Sorting + Skip Duplicates: Sort the input first so equal values sit next to each other, then skip a value when it repeats its neighbor at the same decision level. This deduplicates the output without needing a set of seen subsets.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Sort nums so duplicates are adjacent. Then run a backtracking DFS: at each call, record the current partial selection as a subset, then try extending it with each remaining element. To avoid duplicate subsets, when two equal values are both available at the same level of the decision tree, only branch on the first one — the later copies would rebuild subsets we have already produced.

1) Sort nums so equal values are adjacent.
2) Initialize an empty results list.
3) Define a backtracking helper backtrack(start, current):
   a) Append a copy of current to the results (every node in the tree is a valid subset).
   b) For each index i from start to the end of nums:
      i)   If i > start and nums[i] == nums[i - 1], skip it (duplicate at this level).
      ii)  Append nums[i] to current (choose).
      iii) Recurse with backtrack(i + 1, current) (explore).
      iv)  Pop nums[i] off current (un-choose).
4) Call backtrack(0, []) and return the results list.

⚠️ Common Mistakes

• Forgetting to sort first — the duplicate-skip check nums[i] == nums[i - 1] only works when equal values are adjacent.
• Writing the skip condition as i > 0 instead of i > start, which wrongly blocks legitimate runs of duplicates like [2, 2].
• Appending current itself instead of a copy (current[:]), so every recorded subset mutates as the recursion continues.
• Forgetting to pop after the recursive call, leaving stale elements in current.

4: I-mplement

Implement the code to solve the algorithm.

def subsets_with_dup(nums):
    nums = sorted(nums)  # Sort so duplicates sit next to each other
    subsets = []

    def backtrack(start, current):
        # Every node in the decision tree is a valid subset
        subsets.append(current[:])
        for i in range(start, len(nums)):
            # Skip duplicates at the same tree depth to avoid repeated subsets
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])       # Choose
            backtrack(i + 1, current)     # Explore
            current.pop()                 # Un-choose

    backtrack(0, [])
    return subsets

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • After sorting, nums = [1, 2, 2].
  • backtrack(0, []) records [], then branches on index 0 (value 1).
  • backtrack(1, [1]) records [1], then branches on index 1 (value 2).
  • backtrack(2, [1, 2]) records [1, 2], then branches on index 2 (value 2).
  • backtrack(3, [1, 2, 2]) records [1, 2, 2] and returns (no indices left).
  • Back at backtrack(1, [1]), index 2 is skipped because nums[2] == nums[1] and 2 > start — this is what prevents a second copy of [1, 2].
  • Back at the top level, index 1 (value 2) branches: [2] and [2, 2] are recorded; index 2 is skipped at the top level for the same reason.
  • Output: ], [1], [1, 2], [1, 2, 2], [2], [2, 2 — matches the expected output with no duplicate subsets.

• Input: nums = []

  • backtrack(0, []) records [] and the loop body never runs.
  • Output: [[]]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of elements in nums.

• Time Complexity: O(N * 2^N) — there are at most 2^N subsets, and copying each subset into the results costs up to O(N). The initial sort adds O(N log N), which is dominated.
• Space Complexity: O(N) auxiliary space for the recursion stack and the current selection (the output list of up to 2^N subsets is not counted as auxiliary space).