回溯问题：491 && 46

• 491.递增子序列
• • 题目分析
  • 代码
• 46.全排列
• • 分析
  • 代码

491.递增子序列

链接直达

题目分析

• 和组合40还是很像的【4.17打开过】，两者都是横向遍历的时候需要考虑去重问题

• 这里和40中不同点在于，此题不可排序，因为题目要求递增子序列，一旦排序，那么其实就是和40一样的解法了。这里的去重也是十分关键

• 40中我们解决这个去重问题，使用了used数组，这里同样，还是使用used数组进行去重。40中去重，当used[i - 1] == true的时候，我们在横向遍历每一层的时候表示这个元素没有被访问过，可以加入。如果是false，就是访问过，所以要跳过。当时我们写的if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)这段代码，所限制的同一层的数据，也就是横向的数据。在纵向递归的时候used[i - 1] 都是true，不可能会执行这个

• 但是此题也是如此，我们需要在横向设置限制，限制后面出现的元素，跟本层有相同。但是这题我们的数据是乱序的，假设我们依旧使用这个used的true和false来区分，某一个数值是否被遍历过，那么将会出现一个问题。以【4，4，6，7，4】为例子，每一次进入for的时候，都会判断如下：

  if(used[nums[i] + 100]==false || (path.size() > 0 && nums[i] < path.get(path.size() - 1))){      continue;}

  这时候本身used就是初始化为false，就会一直continue。什么也不输出，所以这是不可取的。

• 我们采用一种十分巧妙的方式，在横向遍历的时候，也就是对于每一层来说，存储一个used。这一层的元素，公用这一个used。那么就可以达到每一层去重，但是也不影响纵向递归进去的过程了

代码

class Solution {    List<List<Integer>> returnArr = new ArrayList();    List<Integer> path = new ArrayList();    public List<List<Integer>> findSubsequences(int[] nums) { if(nums.length == 0 || nums.length == 1){     return returnArr; }    back(nums, 0); return returnArr;    }    public void back(int[] nums, int startindex){ if(path.size() > 1){     //最少两个     returnArr.add(new ArrayList(path)); } //横向遍历的是相同的used，纵向遍历就不同了 boolean [] used = new boolean[205]; for(int i = startindex; i < nums.length; i++){     if(used[nums[i] + 100]==true || (path.size() > 0 && nums[i] < path.get(path.size() - 1))){  continue;     }  path.add(nums[i]);  used[nums[i] + 100] = true;  back(nums, i + 1);  path.remove(path.size() - 1);  // // System.out.print(path);  // System.out.print("==");  // System.out.println(i); }    }}

46.全排列

链接直达

分析

套用回溯模板三大步骤还是很简单的

• 排列问题我们就要考虑顺序了，每一次其实从数组第一个元素开始纵向递归就好了，递归的过程中，跳过已经取过的元素

• 图解，判断是否元素被取过，使用contains就可以了

• 

代码

class Solution {    public List<List<Integer>> res = new ArrayList();    public List<Integer> path = new ArrayList();    public List<List<Integer>> permute(int[] nums) { if(nums.length == 0){     res.add(new ArrayList<>(path));     return res; } if(nums.length == 1){     path.add(nums[0]);     res.add(new ArrayList<>(path));     return res; } back(nums); return res;    }    public void back(int[] nums){ if(path.size() == nums.length){     res.add(new ArrayList<>(path));     return; } for(int i = 0; i < nums.length; i++){     if(path.contains(nums[i])){    continue;     }     path.add(nums[i]);     back(nums);     path.remove(path.size() - 1); }    }}