Backtracking is a general algorithm … that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
https://en.wikipedia.org/wiki/Backtracking
Note: This is the second part for BFS, DFS and Backtracking. The first part is here: [Leetcode for Interview]DFS, BFS, and Backtracking I.
What is backtracking?
While applying DFS to search through a graph, once we determine that the subgraph does not contain a valid result, we can stop here and ‘backtrack’ to the parent node, and then try other routes. So to put it in a simple way, backtracking is DFS plus pruning. Don’t be scared about these concepts, let’s go through a few examples and you will find out that it is quite intuitive.
Leetcode Questions:
- 22. Generate Parentheses – Medium
- 39. Combination Sum – Medium
- 40. Combination Sum II – Medium
- 216. Combination Sum III – Medium
- 46. Permutations – Medium
- 47. Permutations II – Medium
- 51. N-Queens – Hard
- 52. N-Queens II – Hard
- 78. Subsets – Medium
- 90. Subsets II – Medium
- 131. Palindrome Partitioning – Medium
Examples
Normal strategies in the recursion function:
1. Set up an exit condition – when the exit conditions are met, jump out of the recursion.
2. If not exiting, check whether it’s qualified to go to the next level.
3. If it’s qualified to move to the next level, call recursion.
3. After returning from the next level, remember to restore the parameters to the original state.
Please note that, I’ve insert the above four steps into the codes below in comment, so you know where to put them.
39. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations incandidateswhere the candidate numbers sums totarget. The same repeated number may be chosen from candidates unlimited number of times. Note: a. All numbers (includingtarget) will be positive integers. b. The solution set must not contain duplicate combinations. Examples: Input: candidates =[2,3,6,7],target =7Return: [ [7], [2,2,3] ]
This is a typical backtracking problem. To solve it, we can exhaust all possible combinations using DFS, plus pruning – once we found the sum exceeds the target, we can stop and return. Therefore, for the recursion function helper(), we need to keep track of the combination, the difference between our current sum and the target, and the index as we want to avoid duplicates by only moving forward without looking back while looping through the candidates.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret,n = [],len(candidates)
def helper(combination=[],remaining=target,ind=0):
# 1. set an exit condition
if remaining == 0:
ret.append(combination[:])
else:
for i in range(ind,n):
# 2. check if it's possible to move to next level
if candidates[i] <= remaining:
# 3. if it's qualified, change the parameters accordingly
# and call recursion
combination.append(candidates[i])
remaining -= candidates[i]
helper(combination,remaining,i)
# 4. after returning, backtrack as restoring the parameters
combination.pop()
remaining += candidates[i]
helper()
return ret
Apart from that, when we are about to explore the further level, if we create the new parameters instead of modifying the original ones, we don’t have to restore them later. Codes are shown below:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret,n = [],len(candidates)
def helper(combination=[],remaining=target,ind=0):
# 1. set an exit condition
if remaining == 0:
ret.append(combination[:])
else:
for i in range(ind,n):
# 2. check if it's possible to move to next level
if candidates[i] <= remaining:
# 3. if it's qualified, change the parameters accordingly
# and call recursion
helper(combination+[candidates[i]],remaining-candidates[i],i)
helper()
return ret
46. Permutations
Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Similarly, we will again exhaust all possibilities – each time we will try to add one element from the input to our list, until the length of the list equals to the length of the input – unless that we found some elements are in the list already, then we will skip them.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ret,n = [],len(nums)
def helper(combin=[]):
# 1. set an exit condition
if len(combin) == len(nums):
ret.append(combin[:])
else:
for e in nums:
# 2. check if it's possible to move to next level
if e in combin:
continue
# 3. if it's qualified, change the parameters accordingly
# and call recursion
combin.append(e)
helper(combin)
# 4. after returning, backtrack as restoring the parameters
combin.pop()
helper()
return ret
Or, like what we do in 39. Combination Sum, we can create the new variables instead of touching the original ones.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ret = []
def helper(remaining=nums,cur=[]):
# 1. set an exit condition
if remaining == []:
ret.append(cur)
else:
for i in range(len(remaining)):
# 3. if it's qualified, change the parameters accordingly
# and call recursion
helper(remaining[:i]+remaining[i+1:],cur+[remaining[i]])
helper()
return ret