sko.kr

Algorithms - 18. Subsets (Power Set)

algorithmsbacktrackingrecursionsubsetspower-setcombinatorics
By sko•10/9/2025•8 min read

When to use the Subsets Algorithm

Use the Subsets algorithm when you need to generate all possible combinations or selections from a collection. While most commonly used for finding all subsets (power set), it can be adapted for:

  • Power set generation (classic use case - all possible subsets)
  • Combination problems (choosing k items from n)
  • Permutation variants (with modifications to the decision tree)
  • Knapsack problem variants (exploring all possible item selections)
  • Feature selection in machine learning (all possible feature combinations)
  • String subsequences (all possible character selections maintaining order)
  • Any problem where you need to explore all possible "include/exclude" decisions for each element

Example problem

Team Formation: Given a list of players [1, 2, 3], find all possible team formations (including empty team and full team).

For players [1, 2, 3]:

  • Empty team: []
  • Single player teams: [1], [2], [3]
  • Two player teams: [1,2], [1,3], [2,3]
  • Full team: [1,2,3]

Answer: 8 possible teams total (2^3 = 8), representing every possible selection of players.

What the Subsets Algorithm Actually Does

The Subsets algorithm systematically explores a binary decision tree where at each level, you decide whether to include or exclude an element. It provides a way to generate all 2^n possible combinations.

Think of it like packing for a trip with n items:

  • For item 1: "Should I pack this?" → Yes or No
  • For item 2: "Should I pack this?" → Yes or No
  • Continue for all n items...

How the Algorithm Works

The Decision Tree Approach - "Include or Exclude"

When processing element at index i:

  1. Make a copy of current subset state
  2. First branch: Include the element, then recurse on remaining elements
  3. Second branch: Exclude the element, then recurse on remaining elements
  4. When no elements remain: we've made all decisions, save this subset

The Backtracking Mechanism

The algorithm uses backtracking to explore both branches:

// Pseudocode of the decision process:
processElement(index, currentSubset):
  if (index >= array.length):
    // All decisions made - save this subset
    saveResult(currentSubset)
    return

  // Branch 1: Include current element
  currentSubset.add(element[index])
  processElement(index + 1, currentSubset)
  currentSubset.remove(element[index])  // Backtrack!

  // Branch 2: Exclude current element
  processElement(index + 1, currentSubset)

When These Decisions Happen

The algorithm makes decisions recursively at each level of the tree:

For [1, 2, 3], the decision tree looks like:

                        []
            Include 1 /    \ Exclude 1
                   [1]      []
          Include 2 / \    / \ Exclude 2
              [1,2]  [1]  [2]  []
         Inc 3 / \   / \  / \  / \ Exc 3
        [1,2,3][1,2][1,3][1][2,3][2][3][]

Final subsets: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

The beauty of this algorithm is that by making a binary decision at each element, we automatically generate all 2^n possible subsets!

Single most important insight

Every subset corresponds to a unique sequence of n binary decisions (include/exclude) - and by systematically exploring both branches at each decision point through backtracking, we guarantee generation of all 2^n possible subsets without duplicates.

Mental note: The algorithm's genius lies in treating subset generation as a series of "include or exclude" decisions. At each element, we only need to decide: "Should I include this element in the current subset?" By exploring both options recursively and backtracking after each exploration, we automatically generate every possible subset exactly once.

Decision Framework

At every element, you face one simple binary decision:

  • Include the element: Add it to current subset, then process remaining elements
  • Exclude the element: Don't add it, just process remaining elements

The key is to explore both branches for every element using backtracking.

Special Case: Handling Duplicates

When the input array contains duplicates (e.g., [1, 2, 2]), we need a modified decision:

  • Include the element: Add it and continue normally
  • Exclude the element AND all its duplicates: Skip all consecutive duplicates

This prevents generating duplicate subsets like having two [1, 2] subsets from different 2's.

Code

// Generate all subsets without duplicates in input
// Time: O(n * 2^n), Space: O(n) for recursion stack
function generateAllSubsets(elements) {
  const allPossibleSubsets = [];
  const currentWorkingSubset = [];

  function exploreDecisionTree(
    currentElementIndex,
    elements,
    currentWorkingSubset,
    allPossibleSubsets
  ) {
    // Base case: We've made a decision for every element
    const allDecisionsMade = currentElementIndex >= elements.length;
    if (allDecisionsMade) {
      // Save a copy of the current subset configuration
      const finalizedSubset = [...currentWorkingSubset];
      allPossibleSubsets.push(finalizedSubset);
      return;
    }

    // Get the element we're currently deciding about
    const elementToDecideOn = elements[currentElementIndex];

    // DECISION FRAMEWORK: Branch 1 - Include this element
    // Choose to include the current element in our subset
    currentWorkingSubset.push(elementToDecideOn);

    // Explore what happens when we include this element
    const moveToNextElement = currentElementIndex + 1;
    exploreDecisionTree(
      moveToNextElement,
      elements,
      currentWorkingSubset,
      allPossibleSubsets
    );

    // Backtrack: Undo the inclusion to explore the other branch
    currentWorkingSubset.pop();

    // DECISION FRAMEWORK: Branch 2 - Exclude this element
    // Choose NOT to include the current element in our subset
    // (No need to modify currentWorkingSubset - just move forward)
    exploreDecisionTree(
      moveToNextElement,
      elements,
      currentWorkingSubset,
      allPossibleSubsets
    );
  }

  // Start exploring from the first element (index 0)
  const startFromFirstElement = 0;
  exploreDecisionTree(
    startFromFirstElement,
    elements,
    currentWorkingSubset,
    allPossibleSubsets
  );

  return allPossibleSubsets;
}

// Generate all unique subsets when input has duplicate elements
// Time: O(n * 2^n), Space: O(n) for recursion stack
function generateUniqueSubsets(elementsWithDuplicates) {
  // Sort array to group duplicate elements together
  const sortedElements = [...elementsWithDuplicates];
  sortedElements.sort((a, b) => a - b);

  const allUniqueSubsets = [];
  const currentWorkingSubset = [];

  function exploreWithDuplicateHandling(
    currentElementIndex,
    sortedElements,
    currentWorkingSubset,
    allUniqueSubsets
  ) {
    // Base case: We've processed all elements
    const allElementsProcessed = currentElementIndex >= sortedElements.length;
    if (allElementsProcessed) {
      const finalizedSubset = [...currentWorkingSubset];
      allUniqueSubsets.push(finalizedSubset);
      return;
    }

    const currentElement = sortedElements[currentElementIndex];

    // DECISION FRAMEWORK: Branch 1 - Include this element
    // Add current element to our working subset
    currentWorkingSubset.push(currentElement);

    // Continue exploring with this element included
    const nextElementIndex = currentElementIndex + 1;
    exploreWithDuplicateHandling(
      nextElementIndex,
      sortedElements,
      currentWorkingSubset,
      allUniqueSubsets
    );

    // Backtrack: Remove the element to explore exclusion branch
    currentWorkingSubset.pop();

    // DECISION FRAMEWORK: Branch 2 - Exclude this element AND all its duplicates
    // Skip over all consecutive duplicates to avoid duplicate subsets
    let skipToIndex = currentElementIndex + 1;

    // Keep skipping while we see the same element
    while (skipToIndex < sortedElements.length) {
      const nextElement = sortedElements[skipToIndex];
      const isDuplicate = nextElement === currentElement;

      if (isDuplicate) {
        skipToIndex++;
      } else {
        break; // Found a different element, stop skipping
      }
    }

    // Continue exploration from the first different element
    exploreWithDuplicateHandling(
      skipToIndex,
      sortedElements,
      currentWorkingSubset,
      allUniqueSubsets
    );
  }

  // Begin exploration from the first element
  const startIndex = 0;
  exploreWithDuplicateHandling(
    startIndex,
    sortedElements,
    currentWorkingSubset,
    allUniqueSubsets
  );

  return allUniqueSubsets;
}

// === EXAMPLE USAGE: Team Formation Problem ===
const players = [1, 2, 3];
console.log(`Finding all possible teams from players: [${players}]`);

const allPossibleTeams = generateAllSubsets(players);
console.log("All possible team formations:");
allPossibleTeams.forEach((team) => {
  if (team.length === 0) {
    console.log("  [] - Empty team (no players selected)");
  } else if (team.length === 1) {
    console.log(`  [${team}] - Solo team`);
  } else if (team.length === players.length) {
    console.log(`  [${team}] - Full team (all players selected)`);
  } else {
    console.log(`  [${team}] - Partial team`);
  }
});

console.log(`\nTotal possible teams: ${allPossibleTeams.length}`);
console.log(
  `Formula check: 2^${players.length} = ${Math.pow(2, players.length)}`
);

// === EXAMPLE WITH DUPLICATES ===
const playersWithDuplicates = [1, 2, 2];
console.log(`\nHandling duplicate players: [${playersWithDuplicates}]`);

const uniqueTeamFormations = generateUniqueSubsets(playersWithDuplicates);
console.log("Unique team formations (no duplicate teams):");
uniqueTeamFormations.forEach((team) => {
  console.log(`  [${team.join(", ")}]`);
});

console.log(`\nTotal unique teams: ${uniqueTeamFormations.length}`);
console.log("Note: We avoid duplicate [1,2] teams from different 2's!");

Doubt buster

Common doubt: "The algorithm adds elements then immediately removes them with backtracking. Isn't this inefficient? Why not just create new arrays for each recursive call instead?"

Why you might think backtracking is inefficient

Looking at the code, it seems wasteful:

currentSubset.push(nums[index]);    // Add element
generateSubsets(index + 1, ...);    // Recurse
currentSubset.pop();                // Remove the same element immediately!

You might think: "Why not just pass a new array [...currentSubset, nums[index]] to each recursive call and avoid all this push/pop business?"

Why this thinking misses the key optimization

Let's compare both approaches for generating 8 subsets from [1, 2, 3]:

Approach A: Creating new arrays (seemingly simpler)

function subsetsNewArrays(nums, index = 0, current = []) {
  if (index >= nums.length) {
    return [current];
  }

  // Create NEW array for include branch
  const withElement = [...current, nums[index]];

  // Create NEW array for exclude branch (copy of current)
  const withoutElement = [...current];

  return [
    ...subsetsNewArrays(nums, index + 1, withElement),
    ...subsetsNewArrays(nums, index + 1, withoutElement),
  ];
}

Memory cost: For n elements, we create 2^n arrays, each averaging n/2 elements

  • Total memory: O(n * 2^n) for all the intermediate arrays
  • Array creation overhead: 2^n array allocations

Approach B: Backtracking with single array (our approach)

// We reuse THE SAME array throughout the entire recursion!
const currentSubset = []; // Only ONE array allocated

Memory cost:

  • Only ONE working array that we modify and restore
  • Maximum size: n elements (when we include everything)
  • Total memory: O(n) for recursion stack + O(n) for the single working array

Concrete example: Memory usage for [1,2,3]

Without backtracking (new arrays):

Level 0: []                     → 1 array created
Level 1: [1], []                → 2 arrays created
Level 2: [1,2], [1], [2], []   → 4 arrays created
Level 3: [1,2,3], [1,2], ...   → 8 arrays created
Total: 15 intermediate arrays created during recursion!

With backtracking:

Uses the SAME single array throughout:
[] → [1] → [1,2] → [1,2,3] → [1,2] → [1] → [1,3] → ...
     push   push    push      pop    pop   push

Total: 1 array reused for all operations!

Why backtracking is actually MORE efficient

  1. Memory efficiency: O(n) vs O(n * 2^n) space for intermediate arrays
  2. Cache locality: Reusing the same array keeps it in CPU cache
  3. Allocation overhead: 1 allocation vs 2^n allocations
  4. Garbage collection: No intermediate arrays to clean up

The key realization

Backtracking isn't about the elements - it's about the STATE:

  • We're not "wasting work" by adding then removing
  • We're efficiently exploring a decision tree by modifying and restoring state
  • The push/pop operations are O(1) and much faster than array creation
  • We only create new arrays when we find a complete subset (the [...currentSubset] in base case)

Real-world performance difference

For an array of 20 elements (generating 1,048,576 subsets):

  • New arrays approach: Creates over 2 million intermediate arrays
  • Backtracking approach: Uses 1 array, modified 2 million times
  • Performance: Backtracking is ~3-5x faster and uses ~100x less memory

The beauty of backtracking is that it lets us explore an exponential solution space with linear auxiliary space by carefully managing state through modifications and restorations

← Back to Blog