【leetcode24】

作者

39. 组合总和

  1. class Solution:
  2.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
  3.         res=[]
  4.         path=[]
  5.         def f(index):
  6.             if sum(path)==target:
  7.                 res.append(path[:])
  8.                 return
  9.             elif sum(path)>target:
  10.                 return
  11.             for i in range(index,len(candidates)):
  12.                 path.append(candidates[i])
  13.                 f(i)
  14.                 path.pop()
  15.         f(0)
  16.         return res

和其他题差异点在13行，因为可以重复选择元素所以不写f(i+1)

22. 括号生成

  1. class Solution:
  2.     def generateParenthesis(self, n: int) -> List[str]:
  3.         res=[]
  4.         path=[]
  5.         def f(l,r):
  6.             if len(path)==n*2:
  7.                 res.append(''.join(path))
  8.                 return
  9.             if l<n:
  10.                 path.append("(")
  11.                 f(l+1,r)
  12.                 path.pop()
  13.             if r<l:
  14.                 path.append(")")
  15.                 f(l,r+1)
  16.                 path.pop()
  17.         f(0,0)
  18.         return res
没有for循环的回溯
需要分左右两种情况
需要在任何位置右括号数量大于左括号（隐含条件if r>l:return)

发表评论