39. Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
思路：从无元素重复的candidates中找和为target的组合，每一个组合中candidates中的元素可以被多次重复选取。
这道题和昨天的非常类似，只不过昨天的不能重复选取。
在今天这道题中，
1. 允许重复选择同一数字：递归调用 self.backtracking 时传入的 startIndex 是 i 而不是 i+1。这意味着在每一层递归中，都可以重新选择当前正在考虑的数字。例如，如果 candidates[i] 是一个有效的选择，它可以在同一路径中多次被选择。（昨天那道题目里，元素不能被重复选取，所以传入的startIndex 是i+1）
2. 避免重复的组合：即使一个数字可以被多次选择，通过从 startIndex 开始循环，算法仍然确保了不会生成重复的组合。这是因为在每一层递归中，只考虑 startIndex 之后的元素（包括 startIndex 本身），这意味着你不会在后续的递归中重新考虑之前已经处理过的元素。例如，如果组合 [2, 3] 已经被考虑过，那么在后续的递归中就不会再生成 [3, 2] 这样的组合，因为当处理到数字 3 时，递归不会回溯到数字 2。
solution:
class Solution(object):
def backtracking(self, candidates,target,cur_sum,path,startIndex,result):
if cur_sum == target:
result.append(path[:])
return # 别忘记这个return！！
if cur_sum > target:
return
for i in range(startIndex, len(candidates)):# 因为这里给的candiates是没有重复的，所以才可以这样遍历子节点而不用担心生成的path会重复。
cur_sum += candidates[i]
path.append(candidates[i])
self.backtracking(candidates,target,cur_sum,path,i,result)
path.pop()
cur_sum -= candidates[i]
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = []
self.backtracking(candidates,target,cur_sum=0,path=[],startIndex=0,result=result)
return result40. Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
这道题和上一题不一样之处在于，备选数组里有元素是重复的，并且是不放回采样。
不放回采样：要做到不放回采样，backtrack的startIndex就不用i+1，因为在上一级被选过的元素，在下一级是不可以选的。（上一题是放回采样，所以是startIndex=i）
原数组里有重复但避免重复的组合：避免选出来的有效path因为原数组有重复而重复。上一题的思路里说过，如果被选元素没有重复，避免path重复的办法（比如出现[2,3]或者[3,2]），是通过每次for循环中之考虑startIndex之后的元素（注意区分这里和backtrack里startIndex=i+1的意思，这里指的是一次backtrack内，即startIndex已经定了，如果是放回采样，startIndex和上一级的startIndex相同，但是for循环里依然是从startIndex及之后采样的。）
但是这道题里被选元素有重复，所以在for循环的时候要去掉这样的元素，不然在同一层里，两个值相同的元素分别被选中，他们各自之后的值却有机会也形成一样的排列组合，这样的path就可能出现重复了。最简单去重复的办法就是先对数组进行排序，然后在for循环的时候一旦遇到和上一个备选元素一样的被选元素时，就continue过掉这次循环。只有排序树值发生跳变，即当前元素和上一个被选元素值不同时，才会继续。
小结：
1. 不放回采样和放回采样影响backtrack的startIndex，放回就i，不放回就i+1
2. 原数组有重复就排序后在for循环里去重，如果没有重复，就直接for循环，且可以以当前path的长度来剪枝。
3. 剪枝可以根据已有的元素的个数是否都已经大于了所需的sum(前提是都为正数)，或者startIndex之后的元素的个数已经不满足于path里剩余的元素个数(前提是不放回取样)。不过感觉最好画出树状图来更方便理解剪枝。
class Solution(object):
def backtracking(self, candidates, target, cur_sum, path, result, startIndex):
if cur_sum == target:
result.append(path[:])
return
if cur_sum > target:
return
for i in range(startIndex, len(candidates)):
if i > startIndex and (candidates[i] == candidates[i-1]): # 这个i > startIndex很巧妙呀，同时防止了startIndex==0且i==0时，candidates[i-1]无效。
continue
cur_sum += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, cur_sum, path, result, i+1)
cur_sum -= candidates[i]
path.pop()
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = []
candidates.sort()
cur_sum = 0
self.backtracking(candidates, target, 0, [], result, 0)
return result
131. Palindrome Partitioning
Given a string s, partition s such that every
substring
of the partition is a
palindrome
. Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
思路：分割回文序列。暴力解法很难写出来，用回溯算法简化写法，遍历所有可能的分割，然后一一判断每个字符串是否为回文序列，是的话加入，否则继续找。这里请注意一个字符也满足回文序列的要求，取这个字符以及判断这个字符的时候要格外注意是否+1。
因为这个字符串是有序的，所以可以认为字符串里的元素都是unique的
class Solution(object):
def is_palindrome(self, s, start, end):
i = start
j = end
while i<j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def backtracking(self, s, start_index, path, result):
if start_index == len(s):
result.append(path[:])
return
for i in range(start_index, len(s)):
#print(i,start_index, self.is_palindrome(s, start_index, i),s[start_index:i+1])
if self.is_palindrome(s, start_index, i): # 注意！这里是i不是i+1。因为当start_index == i的时候，就只有一个元素，自身就是回文序列。但是截取这一个元素要用s[i:i+1]
path.append(s[start_index:i+1])
self.backtracking(s, i+1, path, result)
path.pop()
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
result = []
self.backtracking(s, 0, [], result)
return result
