Leetcoder Day25｜ 回溯part05：子集+排列

491.递增子序列

���定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

• 输入:[4, 7, 6, 7]
• 输出: [[4, 6], [4, 7], [4, 6, 7], [6, 7], [7,7], [4,7,7]]

  说明:

  • 给定数组的长度不会超过15。
  • 数组中的整数范围是 [-100,100]。
  • 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

    在子集中我们是通过排序，再加一个标记数组来达到去重的目的。而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑。本题抽象为树结构过程如下：

    ​

    从上图可以看到，如果在同一个父节点下，同一树层使用过的元素便不再取，如果所取元素小于子序列最后一个元素，也不符合条件。因此，可以设置一个哈希集合，来记录当前所取的值是否被使用过，哈希集合在递归后不用回溯，因为记录的是同一树层的使用情况，新的循环会清空重新记录。

    class Solution {    List res =new ArrayList();    LinkedList path = new LinkedList();    public void backTracking(int[] nums, int startIdx){        if(path.size()>1){            res.add(new ArrayList(path));        }        HashSet record= new HashSet();        for(int i=startIdx;inums[i]) || record.contains(nums[i])){                continue;            }            record.add(nums[i]);            path.add(nums[i]);            backTracking(nums, i+1);            path.removeLast();        }    }    public List findSubsequences(int[] nums) {        backTracking(nums, 0);        return res;    }}

    46.全排列

    给定一个 没有重复 数字的序列，返回其所有可能的全排列。

    示例:

    • 输入: [1,2,3]
    • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

      排列问题不需要使用startIdx因为可以存在重复取值的情况，比如第一次1被取过，形成[1,2,3]，后面还可以再取组成[2,1,3]，但是需要设置一个数组used来记录当前元素在同一path中是否使用过。如果used[i-1]为true，则取下一个元素，因为本题为不重复的元素，所以不用去重。

      class Solution {    List res =new ArrayList();    LinkedList path = new LinkedList();    public void backTracking(int[] nums, boolean[] used){        if(path.size()==nums.length){            res.add(new ArrayList(path));            return;        }        for(int i=0;i