Generate All Subsets (Power Set)

📌 Definition:

📖 Detailed Explanation:

Backtracking builds subsets by, at each index, choosing to include or skip the element; every recursion state is itself a valid subset to record. There are 2^n subsets, so the time is O(n * 2^n). An iterative "double the existing subsets with each new element" approach also works.

💻 Solutions:

• Java
• JavaScript
• Python

public static List<List<Integer>> subsets(int[] a) {
    List<List<Integer>> out = new ArrayList<>();
    backtrack(a, 0, new ArrayList<>(), out);
    return out;
}
private static void backtrack(int[] a, int start, List<Integer> cur, List<List<Integer>> out) {
    out.add(new ArrayList<>(cur));
    for (int i = start; i < a.length; i++) {
        cur.add(a[i]);
        backtrack(a, i + 1, cur, out);
        cur.remove(cur.size() - 1);
    }
}

function subsets(a) {
  const out = [];
  (function backtrack(start, cur) {
    out.push([...cur]);
    for (let i = start; i < a.length; i++) {
      cur.push(a[i]);
      backtrack(i + 1, cur);
      cur.pop();
    }
  })(0, []);
  return out;
}

def subsets(a):
    out = []

    def backtrack(start, cur):
        out.append(cur[:])
        for i in range(start, len(a)):
            cur.append(a[i])
            backtrack(i + 1, cur)
            cur.pop()

    backtrack(0, [])
    return out

🔑 Key Points:

• 2^n subsets -> O(n * 2^n)
• Backtracking: include vs skip each element
• Record the current partial as a subset
• Iterative doubling is an alternative

🌍 Real-World Example: