After solved 1000 medium leetcode found thes patterns — Backtracking

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

Conclusion

--

--

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy

Love podcasts or audiobooks? Learn on the go with our new app.

LORY

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy