After solved 1000 medium leetcode found thes patterns — Backtracking
Explained with a list of high ranking problems
Short story : by end of 2020 I burned out from my work. if happening to you, recommend you read this .
During Covid , I have been solving leetcode problems to resharp the algorithm skillset and pickup new language — python. It returned me more than just offers. I like most of the leetcode problems, they are like a coding gym (If you also happen to be a body builder and stuggle getting results ,read this)for developers . If you want to get deeper understanding of algorithm and data structure, or would like to pick up another new language, solve these problems is a good way.
Continue the leetcode pattern series . this is another one — backtracking . As i did in DFS, BFS and DP ,I will explain with some high ranking problems .
Unlike DP, This algorithm is slow because it is sort of bruteforce . however it is still useful (for not so big data input) because the code is easy to understand .
Core Pattern
@cache
def solve(inputs, current):
if break_condition:
return
if fulfil_target:
add_into_result(current)
return
for i, n in enumerate(inputs):
solve(i, inputs, current_state(current, inputs[i]))The idea is no difference from a normal recursive function : get the inputs, loop through every element and compute state, and pass to next_inputs. next input could be same array, index count from next, or , a different array .repeat the same . in many cases, could add cache decorator to speed up .
Old school. Combination and permutation are 2 classic problems of back tracking .
A Classis problem of back tracking . Thought process : try pick every element of current array, and next picking start from current index (for this problem, every candidate could be resued).
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def comb(start, s, cur):
if s > target:
return
if s == target:
res.append(cur)
return
for i in range(start, len(candidates)):
# start from index i because every index can be used multiple times
comb(i, s+candidates[i], cur +[candidates[i]])comb(0, 0, [])
return res
What if there are dup elements ? cache it before next call .
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
arr = sorted(nums)
res= []
def sub(idx, cur):
res.append(cur[:])
cache = set()
for i in range(idx, len(arr)):
if arr[i] not in cache:
cache.add(arr[i])
sub(i+1, cur+ [arr[i]] )
sub(0, [])
return resPermutation pattern is same. just the thought process here a bit different : pick up every element from array, put it in front of result (next state), repeat same for the rest of array elements.
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def perm(nums, cur):
if not nums:
res.append(cur[:])
return
# loop through the array pick every number then remove it from list
# repeat the process
for i in range(0, len(nums)):
perm(nums[:i]+nums[i+1:], cur+[nums[i]]) # be mindful the state sharing here
perm(nums, [])
return resBoth combination and permutation problems are easy to understand .
Other problems the core idea still same . just the <next_inputs> need to be calculated with helper functions.
Here are 2 more high rating problems .
Thought process. the gole is to split the array of matchsticks into 4 parts, each part with same length. so just try pick every stick into current length, until find the target length or current length > target, cache it .this is “permutation” problem model .
def makesquare(self, matchsticks: List[int]) -> bool:
@lru_cache(None)
def check(arr, cur, width, total):
if cur > width:
return False
if total == 0: # success
return True
if cur == width: # finished one side. continue the other sides
return check(arr, 0, width, total - width)
# still constructing one side. backtracking check all possibilities
for i in range(0, len(arr)):
if check(arr[:i]+arr[i+1:], cur+arr[i], width, total):
return True
return False
s = sum(matchsticks)
if s % 4 != 0:
return False
l = s//4
return check(tuple(matchsticks), 0, l, s)Thought process. track how many still needed and every time start without using voucher then try use every voucher and compare to get best.Yes this issue is DFS + cache .
def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
def can_use(needs, s):
# rule : can not buy any item more than needed
still_need = tuple([t1-t2 for t1,t2 in zip(needs, s[:-1])])
valid = all(x>=0 for x in still_need) # still_need must be >= 0
return valid, still_need
@cache
def dfs(needs, price, special):
if all([n == 0 for n in needs]):
return 0
# try without voucher
res = sum([n * p for n,p in zip(needs, price)])
for s in special: # try use every voucher
ok, still_need = can_use(needs, s)
if ok:
r = dfs(still_need, price, special) + s[-1]
if r < res:
res = r
return res
# convert to tuple for cache
best = dfs(tuple(needs), tuple(price), tuple([tuple(s) for s in special]))
return bestThought process. same idea, just input is different, instead of array now getting left and right counting of brackets, need handle 3 cases (track left and right bracket count) .but the core of problem is a “state tree” state<left, right, current_brakets> .it is a “permutation” problem model with “left”, “right” checking.
def generateParenthesis(self, n: int) -> List[str]:
"""
generate from empty string count left and right parentheses
when left > right: (() . now can append left or right
when left = right: (). now can only append left
when left < right: ()). already invalid. can not proceed
"""
res=[]
def generate(s, left, right, n):
if left>n or right > n:
return
if left == right:
if left == n:
res.append(s)
return
# can only generate left
generate(s+'(', left+1, right, n)
elif left > right:
# can append either left or right
generate(s+'(', left+1, right, n)
generate(s+')', left, right+1, n)
generate('', 0, 0, n)
return resYes, you get the idea. when this “try every combinations/permutations/possibilities of XX” and “store YY state” come into your mind , this is the sign of backtracking problem. don’t afraid of slowness, solve it and make it work first, then consider optimization with a cache or think other options (DP) .this is how we build software as well . the same in solving problems.
More backtracking problems.
17. Letter Combinations of a Phone Number
416. Partition Equal Subset Sum
Conclusion
Backtracking is a bruteforce idea to DFS the possible paths, try apply cache . it is generally slow but many problems could be solved by this idea as long as input not so big, like find permutations, combinations, or possibilities in array or string or matrix .
Hope it helps ! Happy Leetcoding.
