Subsets: include or exclude each element

• Power set – the set of all subsets, including the empty set and the full set.
• Backtracking – a recursive helper carries a start index and the current partial subset.
• Record at every node – add a copy of the current path at every recursion level, not only at leaves.
• Start index – advancing by one prevents reusing earlier elements, generating subsets instead of permutations.
• **O(n * 2^n)** – 2^n subsets, each copied in up to O(n) time.

What is the problem?

Given an array of distinct integers, return all possible subsets. In a banking context, Priya is choosing from n optional account add-ons at National Bank of India, and the product team needs to price every possible combination.

How does the backtracking approach work?

Use a recursive helper with a start index and the current path. At entry, record a copy of the path. Then loop from start to the end: add the element, recurse with start+1, and remove the element (backtrack).

package com.bank.service;

import java.util.*;

public class AddOnPackageEnumerator {

    public static List<List<String>> allSubsets(String[] addOns) {
        List<List<String>> result = new ArrayList<>();
        backtrack(addOns, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(String[] addOns, int start,
            List<String> path, List<List<String>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < addOns.length; i++) {
            path.add(addOns[i]);
            backtrack(addOns, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        String[] addOns = {"Locker", "Insurance", "Overdraft"};
        List<List<String>> packages = allSubsets(addOns);
        System.out.println("All possible packages (" + packages.size() + "):");
        for (List<String> pkg : packages) {
            System.out.println("  " + (pkg.isEmpty() ? "[none]" : pkg));
        }
    }
}

All possible packages (8):
  [none]
  [Locker]
  [Locker, Insurance]
  [Locker, Insurance, Overdraft]
  [Locker, Overdraft]
  [Insurance]
  [Insurance, Overdraft]
  [Overdraft]

Why record at every node, not just leaves?

Recording only at leaves would capture only the full-length subsets. Recording at every node captures the empty subset, single-element subsets, and every intermediate size.

Why does the start index prevent permutations?

Passing i + 1 as the next start ensures that each recursive call considers only elements after the current one, preventing {Insurance, Locker} from being generated when {Locker, Insurance} already exists.

What is the bitmask alternative?

For n elements, enumerate integers from 0 to 2^n - 1. Each bit position indicates whether to include that element.

public static List<List<String>> subsetsBitmask(String[] addOns) {
    int n = addOns.length;
    List<List<String>> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<String> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(addOns[i]);
        }
        result.add(subset);
    }
    return result;
}

What is the time and space complexity?

• **Time: O(n * 2^n)** because there are 2^n subsets and copying each costs up to O(n).
• Space: O(n) for the recursion depth (excluding the output).

What are common mistakes?

The most common mistake is forgetting to add a copy of the path (new ArrayList<>(path)) instead of adding the path reference directly, which would mean all entries in the result share the same mutating list.

// Wrong: all result entries are the same reference
result.add(path); // every entry changes as path mutates

// Correct: snapshot the current state
result.add(new ArrayList<>(path));

How does this extend to subsets with duplicates?

When the input contains duplicates, sort the array first and skip consecutive equal elements at the same recursion level to avoid generating duplicate subsets.

What should a senior engineer know?

A senior engineer recognises that subsets is the foundational backtracking pattern. Combinations (subsets of fixed size k), permutations, and combination sum all build on this structure. The bitmask alternative avoids recursion entirely, which some interviewers prefer.