The O(n) Club: Subsets (Power Set): Why Your Algorithmic FOMO Is Actually Required

The O(n) Club: Subsets (Power Set): Why Your Algorithmic FOMO Is Actually Required

⚡ TL;DR

You need every possible subset of a set of unique integers. Yes, every. All combos: empty, singles, doubles, the full shabang. This isn’t a challenge to be clever—brute force backtracking is as good as it gets. Here’s your Java starter kit:

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

🧠 How Devs Usually Mess This Up

Most folks try to outsmart the math. Some common oopsies:

• Confusing subsets (order doesn’t matter) with permutations (order obsessed). If your output says [1,2] and [2,1], you’re double-dipping!
• Accidentally forgetting the empty set. Yes, it counts as a party attendee (it’s the introvert in the corner).
• Trying to optimize time to less than O(2ⁿ). Spoiler: you can’t. You want every possible subset? You’re paying for every meal on the menu.
• Messing up by changing the current subset in-place and not cloning lists before adding to results—ending up with a hilarious list of identical objects. Classic Java move.

🔍 What’s Actually Going On

Think of every element in the array as a light switch: on (include) or off (exclude). Generate every possible on/off combo and you’ve got your subsets.

Technically? It’s recursion, baby. For each number, you branch: include it or don’t—and you do that for every number in line. Empty set? Check. Everything in? Check. Everything in between? Power set complete.

Bonus: If you picture a binary tree, each path to a leaf is a unique subset. Not as thrilling as Netflix, but at least it ends in exponential options.

🛠️ PseudoCode

• Start with an empty results list.
  List<List<Integer>> res = new ArrayList<>();
• Call backtrack with position 0 and an empty subset:
  backtrack(nums, 0, [], res)
• For each recursion:
  • Add a new copy of your current curr to res.
  • Loop from start to the end of nums:
  • Add the number at i to curr.
  • Recursively continue with i + 1 as your new start.
  • Remove the last element from curr as you unwind (backtrack).

💻 The Code

import java.util.*;
 public class SubsetsPowerSet {
    public List<list>> subsets(int[] nums) {
        List<list>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
     private void backtrack(int[] nums, int start, List
<integer> curr, List<list>> res) {
        res.add(new ArrayList<>(curr)); // Defensive copy saves the day
        for (int i = start; i < nums.length; i++) {
            curr.add(nums[i]);
            backtrack(nums, i + 1, curr, res);
            curr.remove(curr.size() - 1); // Rewind for the next path
        }
    }
     public static void main(String[] args) {
        SubsetsPowerSet sps = new SubsetsPowerSet();
        int[] nums = {1, 2, 3};
        System.out.println(sps.subsets(nums));
    }
}
</list></integer></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• No empty set? Interviewer facepalm. Always add [] (even if the subset is just existential dread).
• Used the same list instance? Whoops, every subset is identical. Always new ArrayList<>(curr) before adding!
• Scaling up? Welcome to Memory Error-land if your nums gets too big. O(n 2ⁿ) space isn’t just a suggestion.
• Using with duplicates? This code assumes all numbers are unique. If not, get ready for Subsets II and more coffee.

🧠 Interviewer Brain-Tattoo

“You can’t avoid exponential regret: if you need every subset, there is no hack—just get comfy and enumerate ’em all.”