# 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 res

Permutation 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 res

Both 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 best

Thought 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 res

Yes, 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.