The O(n) Club: Unique Subsets With Twins (How to Uninvite Duplicate Guests)

The O(n) Club: Unique Subsets With Twins (How to Uninvite Duplicate Guests)

⚡ TL;DR

Need to find every combo of numbers in an array (even if numbers repeat) but only want unique groups? Sort first! Backtracking is your friend—just skip repeated numbers at the right moment.
Here’s the brute-force version (which acts like that one friend who brings uninvited twins to every party):

// Brute-force. Duplicate central:
public List<list>> subsetsWithDup(int[] nums) {
    List<list>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}
void backtrack(List<list>> res, List<integer> temp, int[] nums, int start) {
    res.add(new ArrayList<>(temp));
    for (int i = start; i < nums.length; i++) {
        temp.add(nums[i]);
        backtrack(res, temp, nums, i + 1);
        temp.remove(temp.size() - 1);
    }
}</integer></list></list></list>

// This version makes no effort to avoid duplicate party-crashers. Scroll down for the fix.

🧠 How Devs Usually Mess This Up

It’s tempting to throw classic recursion at this and hope the duplicates just… vanish. If you skip sorting, your duplicate-check is completely blind—if your code is letting through double-dates, this is why. Just as classic recursion can’t spot twins in a crowd, backtracking without skip logic brings you one step closer to recursion regret.

🔍 What’s Actually Going On

Pretend you’re organizing group photos. Some friends look eerily similar (maybe it’s the matching hoodies), and you don’t want photos with the exact same faces more than once. Arranging them by face (aka: sorting) lets you spot the twins. When making each photo, if you see a twin in the same lineup position, only let one through—no need to snap the same shot again and again. Algorithmically, sort first, then skip if “this twin” already got a pic at this lineup spot.

🛠️ PseudoCode

• Sort the array with Arrays.sort(nums);
• Set up your results list and start recursive backtracking.
• At each call, add the current set to results.
• For every index from your current start:
• If i > start && nums[i] == nums[i-1]: skip. We took this twin last round.
• Otherwise, add nums[i] and recurse deeper.
• Backtrack/remove that number—try the next one.

💻 The Code

public List<list>> subsetsWithDup(int[] nums) {
    List<list>> result = new ArrayList<>();
    Arrays.sort(nums); // Twin-spotting
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}
private void backtrack(List<list>> result, List<integer> tempList, int[] nums, int start) {
    result.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // Skip déjà vu
        tempList.add(nums[i]);
        backtrack(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
</integer></list></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Missing the sort means your skip logic fails and you’ll drown in duplicates.
• Edge cases: Empty set ([]) is still a set! All identical numbers? Think [5,5,5]—should give all unique-sized multiples, not clones.
• Complexity: No way out of O(2^n) time—every item is a join-or-skip decision, but handling twins adds just a smidge more checking.
• Results list copies: Always clone your temp list, or you’ll get haunted by mutable subset ghosts.

🧠 Interviewer Brain-Tattoo

Whenever someone says, “Don’t worry about duplicates,” sort the array and smile knowingly. (Even twins can’t fool sorted order.)