39. 组合总和
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
result = []
def backtracking(candidates, target, sum_nums, start_index):
if sum_nums > target:
return
if sum_nums == target:
result.append(path[:])
return
for i in range(start_index, len(candidates)):
path.append(candidates[i])
sum_nums += candidates[i]
backtracking(candidates, target, sum_nums, i)
path.pop()
sum_nums -= candidates[i]
#这里是对数组操作，所以start_index从0开始
backtracking(candidates, target, 0, 0)
return result
40.组合总和II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
result = []
used = [0] * len(candidates)
candidates.sort()
def backtracking(candidates, target, sum_nums, start_index, used):
if sum_nums > target:
return
if sum_nums == target:
result.append(path[:])
return
for i in range(start_index, len(candidates)):
# 判断used[i - 1] == 0，进行树层去重，保留树枝的重复值
if i > 0 and candidates[i] == candidates[i-1] and used[i - 1] == 0:
continue
path.append(candidates[i])
sum_nums += candidates[i]
used[i] = 1
backtracking(candidates, target, sum_nums, i + 1, used)
path.pop()
sum_nums -= candidates[i]
used[i] = 0
backtracking(candidates, target, 0, 0, used)
return result
131.分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
path = []
result = []
def backtracking(s, start_index):
if start_index == len(s):
result.append(path[:])
return
for i in range(start_index, len(s)):
temp = s[start_index : i + 1]
if temp == temp[::-1]:
path.append(temp)
backtracking(s, i + 1)
path.pop()
else:
continue
backtracking(s, 0)
return result
