Backtracking made simple
Tags: leetcode, python, programming, tutorial
Published: 2023-12-25 12:48:58

Yesterday, I could not solve a single backtracking problem in [Leetcode](https://leetcode.com/tag/backtracking/). But I watched some [YouTube videos](https://www.youtube.com/watch?v=Zq4upTEaQyM) to understand the algorithm, and today I am able to solve backtracking leetcode medium problems within 10 minutes. In this blog, I will tell you the trick that I learned to solve any backtracking problems and apply the trick to leetcode problems.

## Introduction:
Backtracking is a general algorithm for finding **all (or some)** solutions to a computational problem that incrementally builds candidates for solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution

![backtracking](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pv7fohi3bdvhkfm110hv.jpg)

## We can easily come up with the backtracking solution by answering the following three questions:

1. What is the goal of the problem?
2. What are the choices that we can make?
3. What is the constraint when making a choice?

## Here's a Python template for a backtracking algorithm:

```python
def backtrack(candidate, problem):

    # check if the goal is reached
    if is_solution(candidate, problem):
        process_solution(candidate, problem)
        return
    
    for next_candidate in generate_candidates(candidate, problem):

        # Check the constraint
        if is_valid(next_candidate, problem):

            # Make a choice
            make_choice(candidate, next_candidate, problem)
            
            # Recursively call the backtracking method
            backtrack(next_candidate, problem)
            
            # Undo the choice (backtrack)
            undo_choice(candidate, next_candidate, problem)

```

## Let's solve the [39. Combination Sum](https://leetcode.com/problems/combination-sum/description/) problem:

> Given an array of **distinct** integers `candidates` and a target integer `target`, return a list of all **unique combinations** of `candidates` where the chosen numbers sum to `target`. You may return the combinations in **any order**.
> The **same** number may be chosen from `candidates` an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
> **Example 1:**
> Input: candidates = [2,3,6,7], target = 7
> Output: [[2,2,3],[7]]
> Explanation:
> 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
> 7 is a candidate, and 7 = 7.
> These are the only two combinations.

Now, let's answer the above three questions:

1. The goal is to find all the combinations of candidates or numbers that sum up to the `target`.
2. The choices are all the numbers in the `candidates` list. We can use the same number many times.
3. The constraint is that if the sum of the current list is greater than the target, we can not choose that number.

## Solution:

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
       self.combinations = []

       # calling the backtracking helper method
       self.backtracking(candidates, target, 0, 0, [])
       return self.combinations

    def backtracking(self, candidates, target, startIndex, currentSum, currentCombination):
        # Check if we reach the goal
        if currentSum == target:
            self.combinations.append(currentCombination.copy())
            return

        for index in range(startIndex, len(candidates)):
            currentSum += candidates[index]

            # Check the constraint
            if currentSum > target:
                currentSum -= candidates[index]
                continue
            
            # Make a choice and call the backtracking function again
            currentCombination.append(candidates[index])
            self.backtracking(candidates, target, index, currentSum, currentCombination)

            # Undo the choice
            currentCombination.pop()
            currentSum -= candidates[index]
```
In the above code, I first initialized the `combinations` list to hold the combinations. Then I called the backtracking method, which takes 5 arguments:

1. candidates - input candidates list
2. target - target number
3. index - start index of the choice list
4. currentSum - sum of the elements in the current list
5. currentCombination - the current combination list
In `backtracking` method, I first checked if I had reached the **goal**, i.e., if the current sum was equal to the target, then I added the copy of the `currentCombination` to the `combinations` list.
I have a for loop which loops from the `startIndex` to the `last` element in the `candidates`. I check the **constraint**, i.e., if the `currentSum` is less than the `target`.
Then, I made the **choice** of adding the element to my `currentCombination` list and called the `backtracking` method recursively.

> **Note:** Since we can use the same element multiple times, I have passed the current index as the value for `startIndex`. If we can't use the same element, then pass `index+1` as the value for `startIndex`.

Finally, **Undo the choice** by removing the element that was added.

## Time and Space Complexities:

- Time complexity: O(N*2^N)
- Space complexity: O(N)
where N is the length of the `candidates` list.

Connect with me on [LinkedIn](https://www.linkedin.com/in/lokeswaran-aj/) and [Twitter](https://twitter.com/lokeswaran_aj).