回溯
17、电话号码的字母组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == '':
return []
phoneMap = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def backtrack(index: int):
if index == len(digits):
combinations.append(''.join(combination))
else:
digit = digits[index]
for ch in phoneMap[digit]:
combination.append(ch)
backtrack(index + 1)
combination.pop()
combination = list()
combinations = list()
backtrack(0)
return combinations
|
22、括号生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left + 1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right + 1)
S.pop()
backtrack([], 0, 0)
return ans
|
39、组合总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def backtrack(i, tmp_sum, tmp):
if tmp_sum > target or i == n:
return
if tmp_sum == target:
res.append(tmp)
return
for j in range(i, n):
if tmp_sum + candidates[j] > target:
break
backtrack(j, tmp_sum+candidates[j], tmp+[candidates[j]])
backtrack(0, 0, [])
return res
|