day25|排列 回溯

三道题目

• 非递减子序列
• 这个用 used 数组，避免同一个数添加到 path 数组里面多次
• 全排列
• 因为是所有可能的全排列， 所以每个数 都从头开始遍历。 同样用used 数组避免一个数添加多次
• 全排列 2
• 由于出现了重复的树，为了保证(a1,a2) 和(a2,a1) 只有一种排序（这里的a1和 a2 数值相同，只是说明遍历过程的两种情况），我们需要规定遍历时候的一个顺序。我们对原数组进行一个排序。 排序完之后因为不是组合所以必须从头开始遍历。 这样我们就无法利用对原数组排序后来避免重复的情况。
• 一个简单的方法就是如果 a1 已经遍历过了，那么我们就自动跳过 a2 的从头遍历。
• 显然此时就是a1 的 used 为 False 的情况（为 True 的情况表示仍然在遍历包含a1的排序）
• 变为代码如下

for i in range(n):
  if used[i]:
    continue
  if i>0 and nums[i]==nums[i-1] and not used[i-1]:
    continue
    used[i]=True
    dfs(path+[nums[i]])
    used[i]=False