# 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

`@cachedef 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 .

78. Subsets

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 .

90. Subsets II

`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.

46. Permutations

`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 .

473. Matchsticks to Square

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)`

638. Shopping Offers

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`

22. Generate Parentheses

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

39. Combination Sum

40. Combination Sum II

77. Combinations

131. Palindrome Partitioning

216. Combination Sum III

377. Combination Sum IV

416. Partition Equal Subset Sum

491. Increasing Subsequences

526. Beautiful Arrangement

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

--

--

A channel which focusing on developer growth and self improvement