🔙 Understanding Subsets with Backtracking in Python

When solving problems that involve generating all combinations or subsets, backtracking is a powerful and elegant technique. In this post, I’ll walk you through how to generate all subsets of a list of numbers using backtracking — and explain every step clearly.

---

✨ What Are Subsets?

A subset is any combination of elements from a set, including:

• The empty set []

• The full set [1, 2, 3]

• Any partial combination like [1, 3] or [2]

For example, for the input [1, 2], all subsets are:

[[], [1], [2], [1, 2]]

---

🔁 Why Use Backtracking?

Backtracking allows us to:

• Explore all possible inclusion/exclusion choices

• Build combinations step by step

• Cleanly undo choices and try alternatives (that’s the "back" part!)

---

🧠 Step-by-Step Logic

Let’s say we want to find all subsets of [1, 2, 3].

1. Start with an empty subset: []

2. At each step, we decide to either:

   • Include the current number

   • Skip it

3. We do this recursively for each index

4. At each decision point, we store a copy of the current path

---

✅ Final Code: Subsets with Backtracking

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # Store a copy of the current path

        for i in range(start, len(nums)):
            path.append(nums[i])        # Include nums[i]
            backtrack(i + 1, path)      # Explore further
            path.pop()                  # Backtrack (remove nums[i])

    backtrack(0, [])  # Start from index 0 with an empty subset
    return result

🧪 Example Usage

nums = [1, 2, 3]
print(subsets(nums))

🖨 Output:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

---

🧩 Visual Recap: Decision Tree

At each index, we branch:

• Include current element → go deeper

• Exclude current element → skip to next

It’s like traversing a binary decision tree of choices (include or exclude).

---

🚀 Where This Helps

This technique forms the foundation for problems like:

• Combinations

• Permutations

• N-Queens

• Word search paths

• Subset sum problems

Mastering backtracking for subsets is the gateway to all of these.