Subsets | BackTracking Explained

Subsets: Given an array nums of unique integers, return all possible subsets of nums.

The solution set must not contain duplicate subsets. You may return the solution in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [7]

Output: [[],[7]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Back tracking: Solves a similar problem as what dynamic programming solves.

The only thing about back tracking is what we care about returning all of the solutions.

So if we are asked to generate all of the possible paths or solutions in a problem, there's a good chance it's back tracking problem.

Alternatively, it could also be that we want to return a valid solution amongst all solutions.What this means is that given a type of question that is asking us a valid solutions, you can tell that its asking for a valid solutions amongst all the solutions.

There are certain constraints in play that prevent all of the solutions from being correct, only a couple of them are correct

This is different from an optimisation question because in an optimization question there is usually only 1 solutions amongst all the solutions.

Because you want either the minimum or maximum.

Backtracking Analogy:

Imagine you're walking down a small alley with three shops:

• Coffee Shop,
• Bookstore
• Gift Shop.

here we want to return all the possible solutions so this is a good time for back tracking.

Now, question introduces constraint and the constraint says that Bookstore cannot be the 2nd place we visit.

if we need to return all possible subsets. This hints of backtracking

what is backtracking??

It's recursion + brute force

function backTracking(start, result) {
 for (let i = start; i < nums.length; i++) {
  backTracking
 }
}

What is Recursion + Brute Force?

Recursion + brute force === BackTracking

1. Recursion: Solving the problem by calling the same function repeatedly for smaller parts of the problem.
2. Brute Force: Trying every possible combination to find the solution (in this case, every possible subset).

For this question generating subsets, the idea is simple:

For each number in the array, you have two choices:

1. Include it in the subset.
2. Exclude it from the subset.

We use recursion to explore all these possibilities step by step until we've tried everything.

Given : [1,2,3], 
return [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

1. Starting with 1, we begin with empty subset. we have two choice:

1. Include 1 : [1],
2. Exclude 1 : []

 At this poin, result =  [[], [1]]

2. we have 2 incoming, we begin with [[], [1]], we will make the same two choices, but this time for both subsets generated from the first choice.

For the subset [], we have two options

1. Include 2: [2]
2. Exclude 2: [] (which is already added in #1)

For the subset [1], we have two options

1. Include 2: [1, 2]
2. Exclude 2: [1] (which is already added in #1)

result = [[],[1], [2], [1, 2]]

3. Incoming 3, we have result = [[],[1], [2], [1, 2]], for each item in the subset we have two option:

• Include
• Exclude

1. For the subset []
2. Include : [3]
3. Exclude: [] (already exist)
4. For the subset [1]:
5. Include: [1, 3]
6. Exclude: [1] (already exist)
7. For the subset [2]:
8. Include: [2, 3]
9. Exclude: [2] (already exist)
10. For the subset [1, 2]
11. Include: [1, 2, 3]
12. Exclude: [1, 2] (already exist)

Result = [[],[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3] ]

It’s straightforward because subsets are essentially a binary decision tree:

• At every step, you choose whether to include or exclude a number.
• By following this approach recursively, you can generate all possible subsets.

This is brute force because we’re explicitly exploring every possibility.

What is Recursion + Brute Force?

1. Recursion: Solving the problem by calling the same function repeatedly for smaller parts of the problem.
2. Brute Force: Trying every possible combination to find the solution (in this case, every possible subset).

For generating subsets, the idea is simple:

For each number in the array, you have two choices:

1. Include it in the subset.
2. Exclude it from the subset.

We use recursion to explore all these possibilities step by step until we've tried everything.

When do we Backtrack?

Backtracking happens when you've fully explored one possibility or branch of choices and need to undo your last decision to explore other possibilities. In simpler terms:

You backtrack after exploring all possibilities that arise from including a particular element, so that you can then explore what happens if you exclude that element.

function backTrack(start, currentSubset) {
    
    currentSubset has all the answer for this term

    for (let i = start; i < nums.length; i++) {
     # Include current element and explore
      backTrack
     # Exclude, now expolore other path
    }
}

const result = []
function backTrack(start, currentSubset) {
    result.push([...currentSubset])
    for (let i = start; i < nums.length; i++) {
      
      // include & explore
      currentSubset.push(nums[i])
     
      // Recurse to build the rest of the subset
      backTrack(i + 1 , currentSubset)

      // exclude & explore
      currentSubset.pop()
    }
}

backTrack(0, [])
return result

Why backtrack(i + 1)?

I just processed nums[i], so now let's only consider the elements that come after nums[i] in the array.

we want to include the next element in the subset and explore all possibilities after that. The i + 1 ensures that:

1. We move to the next element in the array for the next recursion call.
2. We avoid revisiting the same element or going backward, preventing duplicate subsets.

If we didn’t use i + 1, we might accidentally reuse numbers from earlier positions, leading to duplicates or infinite recursion.

Why pop() the currentSubset?

The pop() is essential for backtracking because:

1. It undoes the choice we made in the current step so that we can explore other possibilities.
2. Without pop(), the currentSubset would keep growing and include unwanted elements.

Let’s walk through it for nums = [1, 2, 3]:

1. Start: currentSubset = [].
2. Add 1: → currentSubset = [1].
3. Add 2: → currentSubset = [1, 2].
4. Add 3: → currentSubset = [1, 2, 3].
5. At this point, we save [1, 2, 3] to the result.
6. Now we backtrack:

• Remove 3 → currentSubset = [1, 2].
• Continue exploring subsets without 3.

1. Remove 2 → currentSubset = [1].

• Now explore subsets starting with [1] but without 2.

The pop() step ensures that each recursive call has a clean slate to work with, meaning it doesn't retain changes from the previous recursive path.

Start: []
    ├── Include 1: [1]
    │    ├── Include 2: [1, 2]
    │    │    ├── Include 3: [1, 2, 3] (Save)
    │    │    └── Exclude 3: [1, 2] (Backtrack, Pop 3)
    │    └── Exclude 2: [1] (Backtrack, Pop 2)
    │        ├── Include 3: [1, 3] (Save)
    │        └── Exclude 3: [1] (Backtrack, Pop 3)
    └── Exclude 1: [] (Backtrack, Pop 1)
        ├── Include 2: [2]
        │    ├── Include 3: [2, 3] (Save)
        │    └── Exclude 3: [2] (Backtrack, Pop 3)
        └── Exclude 2: []
            ├── Include 3: [3] (Save)
            └── Exclude 3: [] (Backtrack, Pop 3)

#backTracking #dataStrucutres #algorithms