回溯是一种比较特殊的递归，这种递归有以下两个特点：
1、程序处于尝试搜索的状态，选择条件向某个分支执行，当不满足情况时，回溯到先前的分叉点
2、到达某一终止条件时，记录数据并返回

回溯题的常见模板伪代码：

  1. def backTrack(路径， 可选列表) :
  2.     if 路径长度 == 可选列表长度或满足其他条件：
  3.         记录该路径
  5.     for 可选项 in 可选列表 ：
  6.         添加可选项（另外根据情况判断是否需要将该可选项进行剔除）
  7.         backTrack（路径， 可选列表）
  8.         删除可选项（另外根据情况判断是否需要将该可选项进行回添）

全排列问题

  • 全排列

image.png
全排列的主要目的是取出一个数后就不再放入，那么可以通过visited数组来表示哪个数据是否访问过，进而再取那些并么有被访问过的数据

  1. class Solution {
  2.     List<List<Integer>> list;
  3.     public List<List<Integer>> permute(int[] nums) {
  4.         list = new ArrayList<>();
  5.         boolean[] visited = new boolean[nums.length];
  6.         trackBack(new ArrayList<>(), nums, visited);
  7.         return list;
  8.     }
  10.     public void trackBack(List<Integer> list1, int[] nums, boolean[] visited) {
  11.         if (list1.size() == nums.length) {
  12.             list.add(new ArrayList<>(list1));
  13.             return;
  14.         }
  15.         for (int i = 0; i < nums.length; i++) {
  16.             if (visited[i]) {
  17.                 continue;
  18.             }
  19.             visited[i] = true;
  20.             list1.add(nums[i]);
  21.             trackBack(list1, nums, visited);
  22.             list1.remove(list1.size() - 1);
  23.             visited[i] = false;
  24.         }
  25.     }
  26. }
  • 全排列II


image.png
对于全排列2而言，主要增加难度在于如何处理数组中的重复数据，主要的方式是通过数组排序并判定相邻数据中是否相同。如果相同并且该数据先前是否已经访问过，则跳过；否则对其进行遍历；**

  1. class Solution {
  2.     List<List<Integer>> list;
  3.     public List<List<Integer>> permuteUnique(int[] nums) {
  4.         list = new ArrayList<>();
  5.         boolean[] visited = new boolean[nums.length];
  6.         List<Integer> list1 = new ArrayList<>();
  7.         if(nums.length == 0)
  8.             return list;
  9.         Arrays.sort(nums);
  10.         dfs(list1, nums, visited);
  11.         return list;
  12.     }
  14.     public void dfs(List<Integer> list1, int[] nums, boolean[] visited){
  15.         //设置终止条件：
  16.         if(list1.size() == nums.length) {
  17.             list.add(new ArrayList<>(list1));
  18.             return;
  19.         }
  20.         for(int i = 0; i < nums.length; i++) {
  21.             if (!visited[i]) {
  22.                 //相比于第一类全排列，最关键的判定条件：
  23.                 //首先需要将输入数组进行排序，之后判断，如果位置i上的数等于位置i-1上的数，
  24.                 //并且visited[i-1]=false说明这个数在上一个排列中已经在这个位置放置过了,
  25.                 //那么说明该位置不需要在放置重复的数
  26.                 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
  27.                     continue;
  28.                 visited[i] = true;
  29.                 list1.add(nums[i]);
  30.                 dfs(list1, nums, visited);
  31.                 visited[i] = false;
  32.                 list1.remove(list1.size() - 1);
  33.             }
  34.         }
  35.     }
  36. }

**

组合总和问题

  • 数组总和

image.png
直接套用回溯公式即可解决：

  1. class Solution {
  2.     List<List<Integer>> list;
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         list = new ArrayList<>();
  5.         trackBack(new ArrayList<>(), candidates, target, 0);
  6.         return list;
  7.     }
  9.     public void trackBack(List<Integer> list1, int[] candidates, int target, int index) {
  10.         if (target == 0) {
  11.             list.add(new ArrayList<>(list1));
  12.             return;
  13.         }
  15.         for (int i = index; i < candidates.length; i++) {
  16.             if (target < 0) {
  17.                 break;
  18.             }
  19.             list1.add(candidates[i]);
  20.             trackBack(list1, candidates, target - candidates[i], i);
  21.             list1.remove(list1.size() - 1);
  22.         }
  24.     }
  25. }
  • 组合总和II

image.png
该题关键在于如何处理去重复的问题，一般通过对整个序列进行排序并且在对序列遍历时略过相等部分

  1. class Solution {
  2.     List<List<Integer>> list;
  3.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  4.         list = new ArrayList<>();
  5.         Arrays.sort(candidates);
  6.         trackBack(new ArrayList<>(), candidates, target, 0);
  7.         return list;
  8.     }
  10.     public void trackBack(List<Integer> list1, int[] candidates, int target, int index) {
  11.         if (target == 0) {
  12.             list.add(new ArrayList<>(list1));
  13.             return;
  14.         }
  15.         for (int i = index; i < candidates.length; i++) {
  16.             if (target < 0) {
  17.                 break;
  18.             }
  19.             if (i > index && candidates[i] == candidates[i - 1]) {
  20.                 continue;
  21.             }
  22.             list1.add(candidates[i]);
  23.             trackBack(list1, candidates, target - candidates[i], i + 1);
  24.             list1.remove(list1.size() - 1);
  25.         }
  26.     }
  27. }