Day25--回溯--491. 非递减子序列，46. 全排列，47. 全排列 II

Day25–回溯–491. 非递减子序列，46. 全排列，47. 全排列 II

491. 非递减子序列

思路：

1. 虽然是《子集》问题，但是这个是“子序列”，不能对它进行排序。所以不能用if(i>startIndex&&nums[i-1]==nums[i])的方法去重。此方法只适用于有序的数组。
2. 所以要用set对“同一层”的数字进行去重，如果这一层已经探索过该元素了，continue。
3. 注意要保持非递减性，如果后一个元素比path里最后一个元素（即上一个元素，可能不是紧挨着的）大的话，跳过这个元素。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length < 2) {
            return res;
        }
        backtracking(nums, 0);
        return res;
    }

    private void backtracking(int[] nums, int startIndex) {
        if (path.size() >= 2) {
            res.add(new ArrayList(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

46. 全排列

思路：

1. 属于《排列》问题。排列问题每一层递归，都是从i=0开始，无法用startIndex。所以用used[]数组记录“已经选择”的元素（即在path中的元素），避免重复选择。
2. 注意，现在不是做同一层的元素去重，而是从上至下的元素去重。所以used[]要回溯，递归完要把used[i]变为false，也就是path中没有这个元素了。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        backtracking(nums, used);
        return res;
    }

    private void backtracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

47. 全排列 II

思路：

1. 这个问题就把上两题给结合了。因为原集合里面有重复元素，所以“同一层”要去重；同时，因为是《排列》问题，每层从i=0开始，要对进入path的元素进行去重，也就是从上至下的去重。
2. 故此，需要set来对本层元素进行去重。——可以看到，每进入新一层递归，set都是new的。
3. 需要used[]对进入path的元素进行去重，可一件，used[]是全局唯一的。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        backtracking(nums, used);
        return res;
    }

    private void backtracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

回溯总结

《代码随想录》：

回溯：for循环横向遍历，递归纵向遍历，回溯不断调整结果集

这个回溯章节竟然容易做得脑瓜子晕晕的。第一次做的时候，是在做不下去了，放置了几天，回来从头再做一遍下去，效果好多了。也更容易总结出规律来。

题目类型：

• 组合
  • 最简单的问题，最基础的问题，最容易理解的问题
• 分割
  • 最烧脑的问题
• 子集
  • 注意去重操作，可以对它重新排序（子序列不可排序）
  • 在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。
• 排列
  • 注意这里进入每一层，都是从i=0开始
  • 从上至下的去重，用全局used[]。同一层的去重，用set（排序的话可以用num[i-1]==nums[i]）比较