回溯法通常用来解决决策和路径问题，使用回溯法来解决的的问题通常返回的结果都是一个集合，在计算的过程中还需要进行剪枝。解决回溯问题实际上就是一个决策树的遍历过程，需要思考下面三个问题：

  1. 路径：也就是已经做出的选择
  2. 选择列表：也就是你当前可以做的选择，通常有一个已选择列表和一个可选择列表
  3. 结束条件：也就是到达决策树的底层，无法再做出选择时（通常会在这里做判断，遍历到当前的路径是否满足条件，如果满足则加入到结果集合里面）

其一般的解题模板如下：

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  7.     for 选择 in 选择列表:
  8.         做选择
  9.         backtrack(路径, 选择列表)
  10.         撤销选择

其实会发现这里和DFS的伪代码很像，但是不同之处在于，DFS通常没有撤销选择那一步，DFS一般是一条道路走到黑就可以了，但回溯法因为会记录路径以及当前的选择或被选择情况，当走到其它同级的决策分支时需要将当前分支的决策选择给重置掉

回溯法典型案例

LeetCode 46. 全排列

  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  3.         ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
  4.         if (nums.length <0) {
  5.             return res;
  6.         }
  7.         dfs(nums, new HashSet<Integer>(), new ArrayList<Integer>(), res);
  8.         return res;
  9.     }
  11.     private void dfs(int[] nums, Set<Integer> useSet, List<Integer> path, List<List<Integer>> res) {
  12.         //dfs的终止条件，就是所有元素都用过了
  13.         if (useSet.size() == nums.length) {
  14.            res.add(path);
  15.         }
  16.         //dfs的处理逻辑，要将数组中的每个元素都用到
  17.         for (int i=0; i< nums.length; i++) {
  18.             //如果没有用过这个元素，则进行dfs
  19.             if (!useSet.contains(nums[i])) {
  20.                 path.add(nums[i]);
  21.                 useSet.add(nums[i]);
  22.                 //这里要new一个新的出来，避免下面的清理冲突
  23.                 dfs(nums, new HashSet<>(useSet), new ArrayList<>(path), res);
  24.                 //清理资源，为其它的元素的dfs
  25.                 useSet.remove(nums[i]);
  26.                 path.remove(path.size()-1);
  27.             }
  28.         }
  29.     }
  30. }

LeetCode 47. 全排列 ||

  1. //这个题目和上一个区别就是元素存在重复的，因此就需要对元素进行排序和判重剪枝
  2. class Solution {
  3.     public List<List<Integer>> permuteUnique(int[] nums) {
  4.         List<List<Integer>> result = new ArrayList<>();
  5.         if (nums.length == 0) {
  6.             return result;
  7.         }
  8.         Arrays.sort(nums);
  9.         boolean[] used = new boolean[nums.length];
  10.         dfs(nums, used, nums.length, result, new ArrayList<>());
  11.         return result;
  12.     }
  14.     private void dfs(int[] nums, boolean[] used, int depth, List<List<Integer>> res, List<Integer> path) {
  15.         if (depth == 0) {
  16.             res.add(path);
  17.             return;
  18.         }
  20.         for (int i=0; i<nums.length; i++) {
  21.             //相对于无重复的，这里增加对前一个已经遍历并撤销选中的分支进行减枝
  22.             if (i>0 && nums[i] == nums[i-1] && !used[i-1]) {
  23.                 continue;
  24.             }
  25.             if (!used[i]) {
  26.                 path.add(nums[i]);
  27.                 used[i] = true;
  28.                 dfs(nums, used, depth-1, res, new ArrayList<>(path));
  29.                 used[i] = false;
  30.                 path.remove(path.size()-1);
  31.             }
  32.         }
  34.     }
  35. }

LeetCode 39. 组合总和

  1. class Solution {
  2.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if (candidates.length == 0) {
  5.             return res;
  6.         }
  7.         Arrays.sort(candidates);
  8.         dfs(candidates,0, target, new ArrayList<>(), res);
  9.         return res;
  10.     }
  12.     private void dfs(int[] candidates,int begin, int target, List<Integer> path, List<List<Integer>> res) {
  13.         if (target == 0) {
  14.             res.add(path);
  15.             return;
  16.         }
  17.         if (target < candidates[0]) {
  18.             return;
  19.         }
  20.         for (int i=begin; i< candidates.length; i++) {
  21.             path.add(candidates[i]);
  22.             //当选了i之后，后面的元素就只从i开始，避免返回去又重复
  23.             dfs(candidates, i, target-candidates[i], new ArrayList<>(path), res);
  25.             path.remove(path.size()-1);
  26.         }
  27.     }
  28. }

LeetCode 40.组合总和 ||

  1. class Solution {
  2.      public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if (candidates.length == 0) {
  5.             return res;
  6.         }
  7.         Arrays.sort(candidates);
  8.         dfs(candidates,0, target, new ArrayList<>(), res);
  9.         return res;
  10.     }
  12.     private void dfs(int[] candidates,int begin, int target, List<Integer> path, List<List<Integer>> res) {
  13.         if (target == 0) {
  14.             res.add(path);
  15.             return;
  16.         }
  17.         for (int i=begin; i< candidates.length; i++) {
  18.             //剩下的元素都比target大，直接剪枝
  19.             if (target < candidates[begin]) {
  20.                return;
  21.             }
  22.             //去除重复的元素，进行剪枝
  23.             if (i> begin && candidates[i] == candidates[i-1]) {
  24.                 continue;
  25.             }
  26.             path.add(candidates[i]);
  27.             //当选了i之后，后面的元素就只从i+1开始，避免i位置的元素重复使用
  28.             dfs(candidates, i+1, target-candidates[i], new ArrayList<>(path), res);
  30.             path.remove(path.size()-1);
  31.         }
  32.     }
  33. }