- 解决一个回溯问题实际上是一个决策树遍历的的过程，只需要考虑如下三个步骤：
- 路径：也就是已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：也就是决策树底层，没有选择
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
从根节点出发，根节点有三个选择，[1, 2, 3]，依次尝试遍历这三个选择进入到下一个节点；下一个节点依次已经选择了[1, 2, 3]，无法继续选择已经选择的数字了，比如：已经选择了1，剩下可选的数字就只有[2,3]；依次递归下去直到没有可以选择的数字。
技巧：
-
如果给定可选择的数字是集合，那么可以每次递归前删除被选择的元素，回溯时，就将该元素重新添加回集合中，同时使用辅助数组保存结果；如果是数组，那么不用删除元素，直接将被选择的元素与下一个即将选择的位置进行交换，回溯时再次交换回来即可。
-
如果用的是辅助数组，由于数组传递的方式是引用传递，所以在保存结果时，需要复制一份新的数组，使用[:]既可以复制了
init:
nums=[1, 2, 3]
idx=0，表示已经选择了的数字的数量，在数组中，idx左边的数字表示已经选择的数字，右边表示未选择的数字
loop:
i = 0 当前选择第0个元素
交换待选择的位置和被选择的数：[1, 2, 3]
递归求解以[1]开头，[2, 3]中选择的数组成的组合
再交换回来：[1, 2, 3]
i = 1 当前选择第1个元素
交换待选择的位置和被选择的数：[2, 1, 3]
递归求解以[2]开头，[1, 3]中选择的数组成的组合
再交换回来：[1, 2, 3]
i = 2 当前选择第2个元素
交换待选择的位置和被选择的数：[3, 2, 1]
递归求解以[2]开头，[1, 3]中选择的数组成的组合
再交换回来：[1, 2, 3]
recurrent1:
nums=[1, 2, 3]
idx=1，表示已经选择了的数字的数量，在数组中，idx左边的数字表示已经选择的数字，右边表示未选择的数字
loop:
i = 1 当前选择第1个元素
交换待选择的位置和被选择的数：[1, 2, 3]
递归求解以[1, 2]开头，[3]中选择的数组成的组合
再交换回来：[1, 2, 3]
i = 2 当前选择第2个元素
交换待选择的位置和被选择的数：[1, 3, 2]
递归求解以[1, 3]开头，[2]中选择的数组成的组合
再交换回来：[1, 2, 3]
recurrent2:
nums=[2, 1, 3]
idx=1，表示已经选择了的数字的数量，在数组中，idx左边的数字表示已经选择的数字，右边表示未选择的数字
loop:
i = 1 当前选择第1个元素
交换待选择的位置和被选择的数：[2, 1, 3]
递归求解以[2, 1]开头，[3]中选择的数组成的组合
再交换回来：[2, 1, 3]
i = 2 当前选择第2个元素
交换待选择的位置和被选择的数：[2, 3, 1]
递归求解以[2, 3]开头，[1]中选择的数组成的组合
再交换回来：[2, 1, 3]
recurrent3:
nums=[3, 2, 1]
idx=1，表示已经选择了的数字的数量，在数组中，idx左边的数字表示已经选择的数字，右边表示未选择的数字
loop:
i = 1 当前选择第1个元素
交换待选择的位置和被选择的数：[3, 2, 1]
递归求解以[3, 2]开头，[1]中选择的数组成的组合
再交换回来：[3, 2, 1]
i = 2 当前选择第2个元素
交换待选择的位置和被选择的数：[3, 1, 2]
递归求解以[3, 1]开头，[2]中选择的数组成的组合
再交换回来：[3, 2, 1]
...继续递归
输入数据是集合时：
def backtracking(nums):
n = len(nums)
res = []
def traverse(idx=0, tmp=[]):
if idx == n:
res.append(tmp[:])
return
else:
for e in nums:
nums.remove(e)
tmp.append(e)
traverse(idx+1, tmp)
nums.add(e)
tmp.pop(-1)
traverse()
return res输入数据是数组时：
def backtracking(nums):
n = len(nums)
res = []
def traverse(idx=0):
if idx == n:
res.append(nums[:])
else:
for i in range(idx, n):
# 交换当前位置的数
nums[idx], nums[i] = nums[i], nums[idx]
traverse(idx + 1)
# 交换完还原
nums[idx], nums[i] = nums[i], nums[idx]
traverse()
return res给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
在尝试选择下一个元素时，用集合保存当前这一步选择过的元素，如果已经选择过了，就不递归了。也就是重复步被剪枝了。
def permuteUnique(nums):
n = len(nums)
res = []
def traverse(idx=0):
if idx == n:
res.append(nums[:])
return
else:
# 这样写浪费内存，每次递归都会新建一个集合，可以当做参数传递，然后维护这个集合
check = set()
for i in range(idx, n):
if nums[i] in check:
continue
check.add(nums[i])
nums[i], nums[idx] = nums[idx], nums[i]
traverse(idx+1)
nums[i], nums[idx] = nums[idx], nums[i]
traverse()
return res给定集合，生成集合中元素的全组合。如：[1, 2, 3]的全组合为是[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
def combinationAll(n):
nums = [i+1 for i in range(n)]
res = []
def traverse(k, tmp=[], idx=0):
if k == 0:
res.append(tmp[:])
return
else:
for i in range(idx, n):
tmp.append(nums[i])
traverse(k-1, tmp, i+1)
tmp.pop(-1)
for i in range(n):
traverse(i+1)
return res排列是有序的，有序体现在：每个排列使用元素可以相同，但是只要位置不同那就是不同的排列；而组合是无序的，每个组合，使用的元素都不相同，但是可能有交集。
如：[1, 2, 3]
对于排列，选择2做第一个元素之后，剩下还能选择的还有[1, 3]，也就是不管选择了哪个数nums[i]，除了nums[i]剩下的数都可以选择；对于组合，选择2做第一个元素之后，剩下还能选择的只有[3]，也就是按照原给定数组的顺序，数字nums[i]被选择之后只有nums[i+1:]后面的才能做选择
技巧：在递归时，可以利用函数参数来控制决策树深度达到剪枝的效果，在求组合时，要求从n个数中选取k个数时就可以这样
leetcode78.子集与这道题思路一致，只不过子集多了一个空元素。
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
这道题和前面有两个不同点：(1).允许组合中的元素数值有重复，但是不能是同一个数字；(2).限定了数字之和要为指定的数
对于允许重复，也就是说，在选择了某个数nums[i]之后，可选择的数有nums[i:]而不是nums[i+1:]；限定数字之和可以用决策树剪枝来解决。
def combinationSum(nums, target):
n = len(nums)
res = []
def traverse(target, tmp=[], idx=0):
if target == 0:
res.append(tmp[:])
return
else:
for i in range(idx, n):
t = target - nums[i]
if t < 0:
continue
tmp.append(nums[i])
# 这是组合问题，所以不要从idx开始而是从i开始
traverse(t, tmp, i)
tmp.pop(-1)
traverse(target)
return res前面所说的不重复指的是不能从给定数组中选择已经选择过的数字，而当给定数组已经含有重复数字时，却不能保证有重复的组合，如：nums=[1, 2, 5, 1, 2]，target=7，得到的结果是：[[1,5,1], [2, 5], [5, 2]]，组合中[1, 1, 5]里面有重复的1，但是这两个1是不同的索引，虽然按照顺序选择排除了[1, 1, 5]，但是没办法排除[2, 5]和[5, 2]，这是因为这两组组合中的2虽然相同，但是索引不同，是不同的2。
- 组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
先对数组排个序，这样最后的组合都是排过序的结果，便于我们去重。对于相同数字开头的组合，在选择下一个数字时，同一层的决策树之间是不能有重复的，因此在遍历可以选择的下一个数字时，如果是重复的数字就剪枝，比如说：[1, 1, 1, 2]， 求和为3的组合，那么最开始可以选的数为[1, 1, 1, 2]，但是同一层中如果出现重复的数值将会导致出现重复的组合，即先选了1，后面再选2，和先选2后面再选1，结果上重复了，因此这个时候，只能选择[1, 2]，只需要保留其中一个1，因此保留第一个数字可以是重复出现的，其他的数字不可以。
def combinationSum2(candidates, target):
n = len(candidates)
candidates.sort()
res = []
def traverse(target, tmp=[], idx=0):
if target == 0:
res.append(tmp[:])
return
else:
for i in range(idx, n):
t = target - candidates[i]
if t < 0:
continue
if i > idx and candidates[i-1] == candidates[i]:
continue
tmp.append(candidates[i])
# 这是组合问题，所以不要从idx开始而是从i开始
traverse(t, tmp, i+1)
tmp.pop(-1)
traverse(target)
return res