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:
- What is the goal of the problem?
- What are the choices that we can make?
- 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 integertarget
, return a list of all unique combinations ofcandidates
where the chosen numbers sum totarget
. You may return the combinations in any order.
The same number may be chosen fromcandidates
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:
- The goal is to find all the combinations of candidates or numbers that sum up to the
target
. - The choices are all the numbers in the
candidates
list. We can use the same number many times. - 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:
- candidates - input candidates list
- target - target number
- index - start index of the choice list
- currentSum - sum of the elements in the current list
- 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 thecurrentCombination
to thecombinations
list. I have a for loop which loops from thestartIndex
to thelast
element in thecandidates
. I check the constraint, i.e., if thecurrentSum
is less than thetarget
. Then, I made the choice of adding the element to mycurrentCombination
list and called thebacktracking
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 passindex+1
as the value forstartIndex
.
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.
Top comments (1)
Amazing post! Welcome to the dev community!