After solved 1000 medium leetcode found thes patterns — Backtracking

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store