Generating subsets (Combinations) and permutations are "canonical" backtracking problems. They involve building a target result step-by-step and "backing up" when you've reached a dead end or a completed result.

Imagine you're at an Ice Cream Shop:

1. Subsets: You can pick any number of toppings. For every topping (Chocolate, Sprinkles, Nuts), you can say YES or NO.
2. Permutations: You are deciding the Order in which you eat the toppings. Does Chocolate go first, then Nuts? Or Nuts first, then Chocolate?

In both cases, you make a choice, see where it leads, and then Take it back (Undo) to see what would happen if you made a different choice.

---

Pattern: Pick or Skip (Subsets)

For every element, you have two choices:

• Include it in the current subset.
• Exclude it from the current subset.
• Complexity: $O(2^n)$.

Pattern: Swap & Recurse (Permutations)

To generate all orderings:

• Every element gets a turn at the first position.
• Then every remaining element gets a turn at the second position, and so on.
• Complexity: $O(n!)$.

---

javascript Standard
/**
 * Generate all Subsets - O(2^n)
 */
function subsets(nums) {
  const result = [];
  
  function backtrack(index, current) {
    if (index === nums.length) {
      result.push([...current]); // Copy current
      return;
    }

    // Choice 1: Pick
    current.push(nums[index]);
    backtrack(index + 1, current);

    // Choice 2: Skip (Backtrack)
    current.pop();
    backtrack(index + 1, current);
  }

  backtrack(0, []);
  return result;
}

/**
 * Generate all Permutations - O(n!)
 */
function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(current) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      
      // Make choice
      used[i] = true;
      current.push(nums[i]);
      
      backtrack(current);
      
      // Backtrack (Undo choice)
      used[i] = false;
      current.pop();
    }
  }

  backtrack([]);
  return result;
}

---

When you see "All Possible Solutions"

Anytime a problem asks for "All possible [combinations/permutations/subsets]", your brain should immediately yell Backtracking.

Common Questions

• Subset Sum: Find if a subset exists that sums to $K$.
• Palindrome Partitioning: Break a string into all possible palindromic substrings.
• Combination Sum: Find all unique combinations that add to a target. Blackwell