Backtracking made simple

Yesterday, I could not solve a single backtracking problem in Leetcode. But I watched some YouTube videos 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

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:

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 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:

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 and Twitter.

Comments

[Elizabeth]

Amazing post! Welcome to the dev community!