216. 组合总和 III
- 思路
- example
- 只使用数字1到9
- 每个数字 最多使用一次
- 回溯
- 宽度：9
- 深度：k
- 剪枝
- sum_ > target
- 集合剩余元素个数
- 图片出处
无重复不可复选
去重：用start控制每次选择的范围（保证不会选重复的数字）
- 复杂度. 时间：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']
- 复杂度. 时间：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): # 实际上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
