回溯2.
这题不太一样的是可以有重复元素，但是只有正整数。所以我觉得思路应该还是一样的。
每一层递归的任务：def helper(candidates, target, startindex):
对于子数组candidates[startindex:]，循环所有小于target的元素，然后call helper(candidates, target-candidates[i], i). 注意最后一个参数是i而不是之前的i+1，因为可以重复。
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
def helper(candidates, target, startindex):
for i in range(startindex, len(candidates)):
if target < candidates[i]:
continue
path.append(candidates[i])
if candidates[i] == target:
res.append(path.copy())
else:
helper(candidates, target-candidates[i], i)
path.pop()
helper(candidates, target, 0)
return res
本题和上一题基本相同，但是按照上一题的方法做会出现重复的组合。那就想怎么去重就可以。一个直观的方法就是每一个path要在加入res之前排好序，这样来查重。但很遗憾，这个方法超时了。
还有一个想法是直接把输入数组排序好，但还是超时了。看来最大的时间开销是把每个path转成tuple。
因此就要想办法不用hashmap来检查是否重复了。看了题解，实际上只需要先排序输入数组，再加入一行判断：
if i > startindex and candidates[i] == candidates[i-1]: continue 就可以达到效果。
这句话的效果可以拆成两部分看：
if i > startindex是赦免i==startindex的数，以[1,1,2,2]为例，也就是[1,1,2,2]的第0个和第2个元素。
candidates[i] == candidates[i-1]则是跳过所有后面的重复数据，也就是[1,1,2,2]的第1个和第3个元素。
建议再以[1,1,2,2]为例手跑一遍，就能领悟当中的精髓之处了。
全部代码如下：
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
def helper(candidates, target, startindex):
for i in range(startindex, len(candidates)):
if target < candidates[i]:
continue
if i > startindex and candidates[i] == candidates[i-1]: continue
path.append(candidates[i])
if candidates[i] == target:
res.append(path.copy())
else:
helper(candidates, target-candidates[i], i+1)
path.pop()
candidates = sorted(candidates)
helper(candidates, target, 0)
return res
新的回溯场景：分割。解题的关键是搞明白递归的子问题：找到s[startindex]开头的回文子串，然后把它切掉，再跳到下一个子问题里面。
例如对于字符串abcdef：
然后你就懂了。还是一种穷举。
def partition(self, s: str) -> List[List[str]]:
res = []
path = []
def isPalindrome(s):
return s == s[::-1]
def helper(s, startindex):
for i in range(startindex, len(s)):
temp = s[startindex:i+1]
if isPalindrome(temp):
path.append(temp)
if i == len(s) - 1:
res.append(path.copy())
else:
helper(s, i+1)
path.pop()
helper(s, 0)
return res
还是一个分割问题，只不过限制多了一些。
限制列举如下：
子问题：找到s[startindex]开头的符合限制的ip子段，然后把它切掉，再跳到下一个子问题里面。
容易写出以下代码：
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
path = []
def isValidIp(s):
return not (s[0] == "0" and len(s) > 1) and 0 <= int(s) <= 255
def helper(s, startindex):
for i in range(startindex, min(startindex+3, len(s))):
num = s[startindex:i+1]
if isValidIp(num):
path.append(num)
if i == len(s) - 1 and len(path) == 4:
res.append(".".join(path))
elif len(path) < 4:
helper(s, i+1)
path.pop()
helper(s, 0)
return res
容易想到一个非回溯解法（一个一个元素加入进之前的所有子集）：
res = [[]]
temp = []
for num in nums:
for l in res:
temp.append(l.copy()+[num])
for t in temp:
res.append(t)
temp = []
return res
更pythonic的写法：
res = [[]]
for num in nums:
res += [i + [num] for i in res]
return res
回溯解法事实上和组合问题的流程是一样的，但是这次不止是输出树叶，而是要输出树中所有的节点。
res = [[]]
path = []
def helper(nums, startindex):
for i in range(startindex, len(nums)):
path.append(nums[i])
res.append(path.copy())
helper(nums, i+1)
path.pop()
helper(nums, 0)
return res