学习资料：https://programmercarl.com/0491.递增子序列.html#算法公开课
排列与组合的区别，不用startIndex，而每个树层都从0开始，但是要跳过已经用过的数（用used判断）
学习记录：
491.递增子序列（添加一个数组used（hash表），来保持数组每个位置上的数的使用情况，没用过为0，用过变成1）
点击查看代码
class Solution(object):
def backtracking(self, nums, startIndex, path, result):
# 与前面子集问题不同，这里只取有两个及以上元素的节点；还是不用考虑终止条件
if len(path) > 1:
result.append(path[:])
# 关键：用数组来表示hash表，用于去重，每次用过的数字作为键对应的值都从0变成1，所以根据值就可以判断是否使用过。
# 一位内数组元素的值在-100到100之间，不大，可用数组，但是因为键是从0开始增加，所以-100的要加100转换为0开始。
used_ls = [0]*201
for i in range(startIndex, len(nums)):
# 去重：1加入的新元素小于已有元素，2这个新元素的值用过了
if (path and nums[i]<path[-1]) or used_ls[nums[i]+100] == 1:
continue
used_ls[nums[i]+100] = 1 # 用hash及时更新元素使用状态
path.append(nums[i])
self.backtracking(nums, i+1, path, result) # 不能重复用同一个元素，i+1
path.pop()
def findSubsequences(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
self.backtracking(nums, 0, [], result)
return result
46.全排列（收集叶子节点）
点击查看代码
class Solution(object):
def backtracking(self, nums, used_ls, path, result):
# 只收集叶子节点
if len(path) == len(nums):
result.append(path[:])
return
# 排列时，每次都考虑所有值，而非startIndex开始，但是不包括已经用过的，去重就用数组
for i in range(len(nums)):
if used_ls[i]:
continue
used_ls[i] = 1
path.append(nums[i])
self.backtracking(nums, used_ls, path, result)
path.pop() # 回溯
used_ls[i] = 0 # 回溯
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
used_ls = [0]*len(nums)
self.backtracking(nums, used_ls, [], result)
return result
47.全排列2（去重，同一树层选取的数的值应该不同，还是数组排序再前后值比大小）
点击查看代码
class Solution(object):
def backtracking(self, nums, used, path, result):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if i>0 and nums[i] == nums[i-1] and used[i-1]==0: # 树层去重：在保证在判断树层的基础上，确定本次使用的树与上一次不同 （usd[i-1]代表是同一层，而非同一数枝！！！！！！）
continue
if used[i]==1: # 保证这个数没被用过，用used位置判断
continue
# 开始递归
used[i] = 1
path.append(nums[i])
self.backtracking(nums, used, path, result)
# 回溯
path.pop()
used[i] = 0
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort() # 给数组排序，用于后续的树层去重
used = [0]*len(nums) # used是用来确定该位置的数有没有被用过
result = []
self.backtracking(nums, used, [], result)
return result
PS:又是心碎的一天，阴转小雨，今天又笔试了一场，能感觉到难度不大都是基础知识，但是非科班的弊端就来了，都不知道。编程题也不会写，能感觉到一点点思路可能就是回溯法，但是感觉火候还不到，还是写不出来。
先学3道题吧，重新安排行程，N皇后，解数独明天再来，累咯
感觉还是别报人工智能岗了，水平不到。
今天吃了好吃的蛋挞，奶味很浓郁，就是一个就好，将将好被腻到