216. 組合總和 III
- 思路
- example
- 只使用數(shù)字1到9
- 每個數(shù)字 最多使用一次
- 回溯
- 寬度：9
- 深度：k
- 剪枝
- sum_ > target
- 集合剩余元素個數(shù)
- 圖片出處
無重復(fù)不可復(fù)選
去重：用start控制每次選擇的范圍（保證不會選重復(fù)的數(shù)字）
- 復(fù)雜度. 時間：O(), 空間: O()
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start, sum_):
if sum_ > n:
return
if len(path) == k:
if sum_ == n:
res.append(path[:])
return
for i in range(start, 9-(k-len(path))+2):
path.append(i)
sum_ += i
backtrack(i+1, sum_)
sum_ -= i
path.pop()
res, path = [], []
backtrack(1, 0)
return res
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def traversal(start):
if len(path) == k:
if sum(path) == n:
res.append(path[:])
return
for i in range(start, 10):
path.append(i)
traversal(i+1)
path.pop()
res, path = [], []
traversal(1)
return res
17. 電話號碼的字母組合
- 思路
- example
- 多個集合求組合
- 特殊情況
- digits == ''
-
invalid 字符莽使？
dict[‘2’] = ['a', 'b', 'c']
- 復(fù)雜度. 時間：O(), 空間: O()
- 用這個版本更好
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def backtrack(digits, idx):
if idx == len(digits):
res.append("".join(path))
return
for ch in map_[digits[idx]]:
path.append(ch)
backtrack(digits, idx+1)
path.pop()
if digits == '': # !!!
return []
res, path = [], []
map_ = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
backtrack(digits, 0)
return res
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def traverse(index):
if index == len(digits):
res.append(''.join(path))
return
for ch in table[digits[index]]:
path.append(ch)
traverse(index+1)
path.pop()
if len(digits) == 0: # !!!
return []
res, path = [], []
table = collections.defaultdict(list)
table = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
traverse(0)
return res
- 下面的寫法比較冗余
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def traversal(start):
if len(path) == n:
res.append(''.join(path))
return
for i in range(start, n): # 實(shí)際上i=1以后都是不必要的奕枢！
for j in range(len(table[digits[i]])):
path.append(table[digits[i]][j])
traversal(i+1)
path.pop()
n = len(digits)
if n == 0: # !!!
return []
table = {'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'}
res, path = [], []
traversal(0)
return res
