算法训练Day29|* 491.递增子序列* 46.全排列* 47.全排列 II

 1class Solution {
 2    List<List<Integer>> result = new ArrayList<>(); // 创建收集结果的结果集
 3    List<Integer> path = new ArrayList<>(); // 收集每个结果
 4    public List<List<Integer>> findSubsequences(int[] nums) {
 5        backtracking(nums, 0); // 回溯函数
 6        return result; // 返回结果集
 7    }
 8    public void backtracking(int[] nums, int startIndex) {
 9        if (path.size() > 1) { // 单个结果集的长度大于1时，即刻加入到结果集中
10            result.add(new ArrayList<>(path));
11        }
12        HashSet<Integer> hs = new HashSet<>(); // 临时的结合hs，用于树层去重
13        for (int i = startIndex; i < nums.length; i++) {
14            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) { // 什么时候去重？树层元素相同时，①路径元素不为空且path中最后一个数值大于当前nums[i] ②同一深度的树层包含同个元素时去重
15                continue;
16            }
17            hs.add(nums[i]); // 收集所有遍历的元素
18            path.add(nums[i]); // 符合条件的元素加入路径中
19            backtracking(nums, i + 1); // 回溯函数继续深度遍历添加符合条件的元素
20            path.remove(path.size() - 1);  // 回溯：结束本层回溯函数，返回上一层继续
21        }
22    }
23}

 1//实现一：
 2class Solution {
 3    List<List<Integer>> result = new ArrayList<>();
 4    List<Integer> path = new ArrayList<>();
 5    public List<List<Integer>> permute(int[] nums) {
 6        backtracking(nums);
 7        return result;
 8    }
 9    public void backtracking(int[] nums) {
10        if (path.size() == nums.length) {
11            result.add(new ArrayList<>(path));
12        }
13        for (int i = 0; i < nums.length; i++) {
14            if (path.contains(nums[i])) {
15                continue;
16            }
17            path.add(nums[i]);
18            backtracking(nums);
19            path.remove(path.get(path.size() - 1));
20        }
21    }
22}

 1class Solution {
 2    List<List<Integer>> result = new ArrayList<>();
 3    LinkedList<Integer> path = new LinkedList<>();
 4    public List<List<Integer>> permute(int[] nums) {
 5        // if (num)
 6        backtracking(nums, path);
 7        return result;
 8    }
 9    public void backtracking(int[] nums, LinkedList<Integer> path) {
10        if (path.size() == nums.length) {
11            result.add(new ArrayList<>(path));
12        }
13        for (int i = 0; i < nums.length; i++) {
14            if (path.contains(nums[i])) { // 终止条件
15                continue;
16            }
17            path.add(nums[i]);
18            backtracking(nums, path);
19            path.removeLast();
20        }
21    }
22}

 1class Solution {
 2    List<List<Integer>> result = new ArrayList<>(); // 存储结果的结果集
 3    List<Integer> path = new ArrayList<>(); // 收集每个符合条件的结果
 4    public List<List<Integer>> permuteUnique(int[] nums) {
 5        boolean[] used = new boolean[nums.length]; // used[]做标记
 6        Arrays.fill(used, false); // 全部赋予false
 7        Arrays.sort(nums); // 排序，便于剪枝（优化搜索）
 8        backtracking(nums, used); // 回溯函数
 9        return result; // 返回结果集
10    }
11    public void backtracking(int[] nums, boolean[] used) {
12        if (path.size() == nums.length) { // 当临时收集的结果等于nums数组长度时，加入到结果集
13            result.add(new ArrayList<>(path)); 
14            return; // 返回上一层
15        }
16        // 横向遍历 
17        for (int i = 0; i < nums.length; i++) {
18            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { // 树层去重
19                continue;
20            }
21            if (used[i] == false) { // 没有遍历过 才进行加入操作
22                used[i] = true; // 置为true表明没有遍历过
23                path.add(nums[i]); // 加入到结果中
24                backtracking(nums, used); // 回溯函数，计息递归
25                path.remove(path.size() - 1); // 去重
26                used[i] = false; //从一下数开始，当前数置为false
27            }
28        }
29    }
30}