代码随想录算法训练营day29 || 491.非递减子序列，46.全排列，47. 全排列||

视频讲解：

回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

491.非递减子序列

思路：组合问题，存在重复元素，强调nums内元素顺序。采用startindex以及set局部已用元素去重；

// 时间复杂度最大是O(n^k)，n是生成树的最大高度，k是ans的长度
// 空间复杂度最大是O(kn)
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        // 类似于子集题目
        if(nums.length == 0)
            return ans;
        backtracking(nums, 0, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, int startindex, boolean[] visited){
        // 遍历到末尾，终止条件
        if(startindex == nums.length){
            return;
        }
        // 新的去重操作，ArrayList的时间效率高于HashSet
        List<Integer> set = new ArrayList<>();
        for(int i=startindex; i<nums.length; i++){
            // 节点处理，仅仅是递增的元素或者list为空时可以加入元素，其他的情况全部continue
            // 此外去重的操作是必须的，且是树层去重，重复的元素在同一个for循环中只可以被选中一次
            if(set.contains(nums[i]))
                continue;
            else if(list.size() == 0 || (list.size()>0 && nums[i] >= list.get(list.size()-1)))
                list.add(nums[i]);
            else
                continue;

            set.add(nums[i]);
            if(list.size()>=2)
                ans.add(new ArrayList<Integer>(list));
            backtracking(nums, i+1, visited);
            // 回溯
            list.remove(list.size()-1);
        }

        return;
    }
}

46.全排列

// 时间复杂度O(n*n(n-1)(n-2)……*2*1)，全排列一共有n(n-1)(n-2)……*2*1)种结果，形成每种结果都需要一次nums的遍历
// 空间复杂度O(n*n(n-1)(n-2)……*2*1)，每一种结果的长度都是n
class Solution {
    
    // 时间效率更快的话就是将list使用数组来代替
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 需要处理特殊情况，backtracking函数中没有涉及特殊情况的处理
        if(nums.length == 0)
            return ans;
        backtracking(nums, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, boolean[] visited){
        if(list.size() == nums.length){
            ans.add(new ArrayList<Integer>(list));
            return;
        }

        // 全排列，元素遍历时可以回头，因此仅仅需要一个visited元素控制已经访问的位置即可
        for(int i=0; i<nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
        }

        return;
    }
}

47. 全排列||?

思路：要求结果不重复，数组内存在重复元素，但是不强调元素顺序不可变，所以使用visited数组结合数组排序解题。

// 时间复杂度O(n^k)，n是nums的长度，k是ans的长度
// 空间复杂度O(nk)
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 出现重复元素，但是强调nums内元素的顺序性，那么是排序结合visited数组进行去重
        // 全排列不需要startindex参数控制遍历仅仅是一个方向，全排列是可以两个方向的
        if(nums.length == 0)
            return ans;
        Arrays.sort(nums);
        backtracking(nums, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, boolean[] visited){
        if(list.size() == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }

        for(int i=0; i<nums.length; i++){
            if(!visited[i]){
                if(i-1>=0 && nums[i] == nums[i-1] && visited[i-1] == false)
                    continue;
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
            
        }

        return;
    }
}

结合非递减子序列、组合、组合II、子集、子集||，关于回溯中去重的方法我们可以做如下总结：

• 组合类问题，仅仅强调nums的访问方向，使用startindex参数即可，也即startindex参数可以保证回溯递归过程中遍历方向始终向后；
• 子集类问题，子集| 强调遍历方向且结果内不可以存在重复结果，使用startindex完成解题；但子集|| 中开始出现nums内存在重复元素，但仍然不强调nums数组内元素的顺序不可变动，所以使用nums排序配以startindex或者nums排序配以startindex以及visited数组即可；
• 非递减子序列，强调遍历方向，存在重复元素，且强调nums内元素顺序不可变动，因此排序配以startindex和visited方法不可行，因此使用了startindex以及局部set查重的操作完成解题；
• 全排列问题，不强调遍历方向，仅仅是每个元素仅仅可以使用一次，因此使用visited数组即可解题；排列|| 中，不强调遍历方向，每个元素使用一次，不可以存在重复的结果，但不强调nums内元素的顺序，所以使用visited数组配以数组排序即可解题。
• 基于以上的内容，我们对所有采用的操作做出如下的归纳：

• startindex，单独使用保证nums遍历方向始终向后，强调遍历顺序的题目使用；
• visited数组，单独使用保证每个元素仅仅被使用一次；排列题目使用；
• 数组排序，单独使用没有意义，联合visited数组和startindex 或 仅联合startindex 或 仅联合visited数组，保证重复的元素在一个for循环中仅仅可以被选中一次，属于全局去重，强调不出现重复结果但不强调nums元素顺序的题目使用；
• set去重，保证重复的元素在一个for循环中仅仅可以被选中一次，属于局部去重，在每一个递归体内新建一个局部set用以去重；强调不出现重复结果且nums元素顺序不可以变的题目中使用；
• 以上的方法直接可以相互配置实现回溯题解题，各个方法的使用需要依据题目的具体要求进行实际的组合或搭配。