491. Non-decreasing Subsequences
排列用startindex
树枝不去重，树层去重
子集问题结果在结点（个数>=2）
class Solution(object):
def findSubsequences(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
path = []
result = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(self,nums, startIndex, path, result):
if len(path) > 1:
result.append(path[:])
# 注意这里不要加return，要取树上的节点
uset = set()
for i in range(startIndex, len(nums)):
if (path and nums[i]<path[-1]) or nums[i] in uset:
continue
uset.add(nums[i])
path.append(nums[i])
self.backtracking(nums,i+1, path, result)
path.pop()
46. Permutations
排列问题不用startindex
因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
path =[]
result = []
used = [False]*len(nums)
self.backtracking(nums,used, path, result )
return result
def backtracking(self, nums, used, path, result):
if len(nums) == len(path):
result.append(path[:])
return #叶子节点收集
for i in range(len(nums)):
if used[i]:
continue
used[i]= True
path.append(nums[i])
self.backtracking(nums, used, path, result)
path.pop()
used[i]=False
47. Permutations II
树层去重（yes），树枝去重（no）
不用startindex
结合46和40
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
path = []
result = []
nums.sort()
used = [False] * len(nums)
self.backtracking(nums, used, path, result)
return result
def backtracking(self, nums, used, path, result):
if len(nums) == len(path):
result.append(path[:])
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
if not used[i]:
used[i] = True
path.append(nums[i])
self.backtracking(nums, used, path, result)
path.pop()
used[i] = False
