491. 非递减子序列
本题不是单纯的去重题目，而是需要保持数字在原数组的顺序。
比如：[4,5,6,7]和[4,6,5,7]相比，后者就不能选择[5,6,7]这个排列，因为违反了设置的顺序。所以去重的方法就只有哈希表。
需要在每一层设置一个哈希表，也就是进入for循环前，来查询是否之前出现过这个数字。由于数字范围是-100～100所以数组就够了。
1、参数和返回值：参数和一般的回溯模版一致，返回值不需要（因为是找到全遍历）
2、终止条件：path长度大于2即可
3、中间处理逻辑：除了回溯的3行以外，需要加两个并列的判断条件，满足一个说明重复了：
（1）当前nums里i指向的数字小于path的最后一个
（2）used数组储存过该数字
此外在添加每个数字的时候还需要设置used == 1，但是不需要在回溯的时候消除，因为是在树的每一层进行标记，而不是进入了递归的树枝。
class Solution(object):
def findSubsequences(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.backtracking(0, [], res, nums)
return res
def backtracking(self, start_idx, path, res, nums):
if len(path) > 1:
res.append(path[:])
# 每一层开始初始化used数组
used = [0] * 201
for i in range(start_idx, len(nums)):
if (path and nums[i] < path[-1]) or used[nums[i]+100] == 1:
continue
path.append(nums[i])
used[nums[i]+100] = 1
self.backtracking(i+1, path, res, nums)
path.pop()
46. 全排列
本题需要明确“层间”还是“树枝”上去重，对于组合问题，前面的数字不能再取，所以是层间去重，回溯的时候不用修改当前层的used数组，但是在树枝上去重的时候，需要在used数组上同样进行回溯，used就是一个用来标记的“伴随”数组。保证回溯之后，这个数字依然可以取到。
1、参数和返回值：除了模版的参数以外，还需要used作为一个数组参数跟着回溯；返回值不需要，因为是全遍历
2、终止条件：全排列，每一个数字都要用到，所以是path和nums数组长度相等的时候
3、中间处理：和上面used设置在for层遍历之前并且不做回溯修改不同，本题used需要在for内（树枝）上修改，并且在回溯之后要消除操作
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
# used数组作为一个参数进入回溯
used = [0] * 21
self.backtracking(nums, [], res, used)
return res
def backtracking(self, nums, path, res, used):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[nums[i]+10] == 1:
continue
used[nums[i]+10] = 1
path.append(nums[i])
self.backtracking(nums, path, res, used)
path.pop()
# used需要回溯
used[nums[i]+10] = 047. 全排列 II
本题是去重+排列的杂交题。
难点在于如何在去重的同时不排除第一次遍历这个排列的情况。
1、参数和返回值：和上一题的排列一致，也是全局的used数组加入到模版写法里，返回值为空
2、终止条件：全排列path长度等于nums长度
3、中间处理：两个判断，分别用于去重和进入递归：
（1）去重：当且仅当前一个数字已经被遍历and现在的数字和之前的是一样的时候，需要continue
（2）进入递归：当前数字未被遍历（注意不是上一个逻辑的else，不然很多不满足三个跳过条件之一的情况也会被加入）
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
used = [0] * 9
self.backtracking(nums, [], res, used)
return res
def backtracking(self, nums, path, res, used):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
# 跳过的判断条件：和前面一个重复，并且前一个已经遍历了（防止第一次被剔除）
if i > 0 and nums[i] == nums[i-1] and used[i-1] == 1:
continue
# 进入下一级的条件：在不重复的前提下，当前节点没有被遍历到
if used[i] == 0:
used[i] = 1
path.append(nums[i])
self.backtracking(nums, path, res, used)
path.pop()
used[i] = 0第29天完结我的天呐！！！我完全就是一整个我的天呐！
要注意细节和对于模版的裁剪依照的是题目的特殊条件和树的裁剪。
