找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

和77.组合同理

class Solution(object):def combinationSum3(self, k, n):""":type k: int:type n: int:rtype: List[List[int]]"""##只使用数字1到9# k=2# n=18tmp=[]res=[]def backtracking(k,n,indx):if sum(tmp)>n: #剪枝操作，元素总和如果已经大于n了，那么往后遍历就没有意义了return if k==0:if sum(tmp)!=n:returnelse:res.append(tmp[:])returnif indx>9:returnfor i in range(indx,10): # (1,6) tmp.append(i) # 1backtracking(k-1,n,i+1) tmp.pop()backtracking(k,n,1)# print(res)return res

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""def mapping(digit):if digit=="2":return list("abc")if digit=="3":return list("def")if digit=="4":return list("ghi")if digit=="5":return list("jkl")if digit=="6":return list("mno")if digit=="7":return list("pqrs")if digit=="8":return list("tuv")if digit=="9":return list("wxyz")res=[]tmp=[]def backtracking(digits,n,indx):if len(tmp)==n:res.append("".join(tmp))return# if not digits: ##本来不应该运行到这里#     return##原来版本：在回溯算法还有深度优先搜索算法中，谨慎用.pop()，因为函数出栈恢复环境的时候可不会把pop()掉的数重新补回来，这个时候还回到原来的地方pop()就会报错说不能对空list执行pop()# digit=digits.pop()digit=digits[indx]opt=mapping(digit)# print(opt)for i in opt: ##tmp.append(i) #dbacktracking(digits,n,indx+1) # "3" 2tmp.pop()digits=list(digits)n=len(digits)if n==0:return []backtracking(digits,n,0)return res

回溯算法的执行顺序 ：当“衍生”的函数执行完后（可以是return，也可以是函数执行到了最后一句），回到之前函数的下一句，继续运行

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""##重点之一：去重## 刚开始循环写的是for candidate in candidates,没有记录for循环的起始位置##这样会导致出现[2,2,3] [3,2,2]这类重复的答案class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""##重点之一：去重## 刚开始循环写的是for candidate in candidates,没有记录for循环的起始位置##这样会导致出现[2,2,3] [3,2,2]这类重复的答案##原始版：每次backtracking都要求sum函数，sum函数时间复杂度O(n)res=[]tmp=[]def backtracking(candidates,target,indx):if sum(tmp)==target:res.append(tmp[:])returnif sum(tmp)>target:returnfor i in range(indx,len(candidates)):tmp.append(candidates[i])backtracking(candidates,target,i)##需要注意，还是要记录位置tmp.pop()backtracking(candidates,target,0)return res##优化版：sum函数用一个局部变量sum_代替，相比原始版时间近乎减半res=[]tmp=[]def backtracking(candidates,target,indx,sum_):if sum_==target:res.append(tmp[:])returnif sum_>target:returnfor i in range(indx,len(candidates)):sum_+=candidates[i]tmp.append(candidates[i])backtracking(candidates,target,i,sum_)##需要注意，还是要记录位置tmp.pop()sum_-=candidates[i]backtracking(candidates,target,0,0)return res##剪枝优化版：排序+剪枝res=[]tmp=[]# sum_=0def backtracking(candidates,target,indx,sum_):if sum_==target:res.append(tmp[:])returnif sum_>target:return# 如果本层 sum + condidates[i] > target，就提前结束遍历，剪枝for i in range(indx,len(candidates)):if sum_ + candidates[i] > target: return sum_+=candidates[i]tmp.append(candidates[i])backtracking(candidates,target,i,sum_)##需要注意，还是要记录位置tmp.pop()sum_-=candidates[i]# 为了剪枝需要提前进行排序candidates.sort()backtracking(candidates,target,0,0)return res

剪枝优化版对比优化版来说加了排序+剪枝
对比优化版，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

但是要注意的是，这种剪枝不一定更高效，因为sort()函数也要耗费时间

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

class Solution(object):def combinationSum2(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""#剪枝优化留着#还是重复问题:之前的重复问题是startindx写错，导致有了[2,2,3]还会出现[3,2,2]#现在的重复问题是数组本身有重复数据，需要排除重复数据影响res=[]tmp=[]def backtracking(candidates,target,indx,sum_):if sum_==target:res.append(tmp[:])returnif sum_>target:returnfor i in range(indx,len(candidates)):if i!=indx:  ##去除重复的组合if candidates[i]==candidates[i-1]:continue# 剪枝，同39.组合总和if sum_ + candidates[i] > target:returnsum_+=candidates[i]tmp.append(candidates[i])backtracking(candidates,target,i+1,sum_)sum_-=candidates[i]tmp.pop()candidates.sort()# 必须提前进行数组排序，避免重复backtracking(candidates,target,0,0)return res

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

class Solution(object):def partition(self, s):""":type s: str:rtype: List[List[str]]"""##回溯+函数判断回文串res=[]tmp=[]# s=list(s)def isreverse(ss):left,right=0,len(ss)-1while left<right:if ss[left]==ss[right]:left+=1right-=1else:return Falsereturn Truedef backtracking(s,indx,n):if indx>=n:res.append(tmp[:])returnfor i in range(indx,n):if isreverse(s[indx:i+1]):tmp.append(s[indx:i+1])backtracking(s,i+1,n)tmp.pop()backtracking(s,0,len(s))return res##回溯+正反序判断回文串res=[]tmp=[]def backtracking(s,indx,n):if indx>=n:res.append(tmp[:])returnfor i in range(indx,n):ss=s[indx:i+1]if ss==ss[::-1]:tmp.append(s[indx:i+1])backtracking(s,i+1,n)tmp.pop()backtracking(s,0,len(s))return res

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

class Solution(object):def restoreIpAddresses(self, s):""":type s: str:rtype: List[str]"""##探讨下0的情况res=[]tmp=[]n=len(s)if n>12: ##字符多于12个时不会有解return []def backtracking(s,indx): if len(tmp)==4 and indx>=n:res.append(".".join(tmp[:]))returnif len(tmp)>4: #returnfor i in range(indx,n):string=s[indx:i+1]if  string != "0" and string.lstrip('0') != string: #Python lstrip() 方法用于截掉字符串左边的空格或指定字符。continue#这个部分说明string != "0"且左边存在'0'，比如“01”这种含有前导 0的例子，此时continue代表跳过if int(string)>=0 and int(string)<=255:tmp.append(s[indx:i+1])backtracking(s,i+1)tmp.pop()backtracking(s,0)return res

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

class Solution(object):def subsetsWithDup(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""#跟子集问题比较起来，需要去下重res=[]tmp=[]n=len(nums)nums.sort()res.append([])def backtracking(indx,n):if indx>=n:returnfor i in range(indx,n):if i!=indx:if nums[i]==nums[i-1]:continuetmp.append(nums[i])res.append(tmp[:])backtracking(i+1,n)tmp.pop()backtracking(0,n)return res

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

class Solution(object):def findSubsequences(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""##本题首先不能排序，因为要求不同的递增子序列##同时要关注重复元素的去重，难点在怎么去除##此时可以引入额外的数组来记录## 同一父节点下的同层上使用过的元素就不能在使用了res=[]tmp=[]n=len(nums)def backtracking(indx,n):if indx>=n:returnstore=[]for i in range(indx,n):if nums[i] not in store:store.append(nums[i])else:continueif tmp:if nums[i]>=tmp[-1]:tmp.append(nums[i])else:continueelse:tmp.append(nums[i])if len(tmp)>=2:res.append(tmp[:])backtracking(i+1,n)tmp.pop()backtracking(0,n)return res

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""res=[]tmp=[]n=len(nums)def backtracking(n):if len(tmp)==n:res.append(tmp[:])returnfor i in range(n):if nums[i] in tmp:continuetmp.append(nums[i])backtracking(n)tmp.pop()backtracking(n)return res

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""## 有逻辑错误的版本res=[]tmp=[]n=len(nums)used=[]def backtracking(n):if len(tmp)==n:res.append(tmp[:])returnstore=[]#去除同层同元素的重复for i in range(n):if i in used: #在一种可能的组合中，用过的元素在下一次列举中不能再用continueif i in store: continuetmp.append(nums[i])used.append(i)store.append(i)backtracking(n)tmp.pop()used.pop()backtracking(n)return res## 正确的版本res=[]tmp=[]n=len(nums)used=[]def backtracking(n):if len(tmp)==n:res.append(tmp[:])returnstore=[]#去除同层同元素的重复for i in range(n):if i in used: #在一种可能的组合中，用过的元素zia不能再用continueif nums[i] not in store:store.append(nums[i])else:continuetmp.append(nums[i])used.append(i)backtracking(n)tmp.pop()used.pop()backtracking(n)return res