LeetCode:491.递增子序列
491. 递增子序列 - 力扣（LeetCode）
1.思路：
创建两个全局变量，一个path收集符合条件的结果，另一个result收集所有符合条件的结果。
当path.size>=2时，符合条件：数量大于1，即刻加入result结果集中。
HashSet临时集合存储所有遍历过的元素，调用hs.contains()方法用于同一递归深度的树层去重！！！
for循环横向遍历实现广度搜索。
2.代码实现：
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}
3.复杂度分析：
时间复杂度：一个元素在回溯一层同时进行for循环和调用递归函数时间耗费为2倍，n层位2^n；n个元素则复杂度为O(n*2^n).
空间复杂度：栈堆空间开销，递归函数消耗栈，层数最大为N,此时时间复杂度为O(n).堆空间开销为集合O(n)。则整体为O(n).
LeetCode:46.全排列
1.思路：
回溯函数不用传入startIndex来限定位置了，直接循环遍历即可，当长度和数组长度相同时加入到结果集中。终止条件：直到path中出现相同元素结束本层循环，继续下一次循环。（终止条件为什么不能是path.size()>nums.length？？）
2.代码实现：
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}
实现2
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}
3.复杂度分析：
时间复杂度:一次遍历为n,n次遍历为n^2.为什么代码随想录给的是O(n!).
空间复杂度：栈开销O(n).堆开销为O(n).
LeetCode:47.全排列 II
1.思路：
2.代码实现：
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}
3.复杂度分析：
时间复杂度：O(n2^n).有疑问：代码随想录O(n!n).
空间复杂度：O(n).
