回溯算法

回溯算法

回溯法一般解决的问题

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式

棋盘问题：N皇后，解数独等等

回溯法的模板

void backTracking(参数) {
  if (终止条件) {
      存放结果;
      return;
  }
  for (选择 本层集合中元素（树中节点孩子树中节点孩子数量就是集合大小）) {
      处理节点;
      backTracking(路径，选择列表); //递归
      回溯，撤销处理结果;
  }
}

LeetCode题目

1.组合

力扣题目链接

回溯三部曲

递归函数的返回值及参数

定义两个全局变量，path存放一个符合条件的结果，res存放所有符合条件的结果

List<Integer> path = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();

还需要定义一个startIndex，记录本层递归中，集合从哪开始遍历的。
每次从集合中选取元素，可选择的范围随着进行而减小，靠startIndex调节。

private void backTracking(int n, int k, int startIndex){}

回溯函数终止条件

path数组大小达到k，说明找到了一个子集大小为k的一个结果。

然后用res二维数组存下path，return终止本层递归。

if (path.size() == k){
    res.add(new LinkedList<>(path));
    return;
}

单层搜索的过程

for循环是横向遍历，递归是纵向遍历。

for (int i = startIndex; i <= n; i++) {
    path.add(i); //处理节点
    backTracking(n, k, i + 1);//递归纵向遍历，注意下一层从i+1开始
    path.removeLast();
}

题解

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }
    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
//剪枝优化：    
//已经选择的元素个数：path.size();
//还需要的元素个数为: k - path.size();
//在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
    private void combineHelper(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

2.组合总和 III

力扣题目链接

回溯三部曲

确定递归函数返回值及其参数

全局变量path，res。sum是path中元素的总和。

List<Integer> path = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
private void helper(int k, int n, int sum, int startIndex) {
}

确定终止条件

当path里元素个数为k，就return。如果path里元素和等于sum的话，add到res里。

if (path.size() == k) {
    if (sum == n) res.add(new LinkedList<>(path));
    return;
}

单层搜索过程

for (int i = startIndex; i <= 9; i++) {
    sum += i;
    path.add(i);
    helper(k, n, sum, i + 1);
    sum -= i;
    path.removeLast();
}

处理过程要和回溯过程一一对应，sum += i对应 sum -= i，add对应removeLast。

题解

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        helper(k, n, 0, 1);
        return res;
    }
    private void helper(int k, int n, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == n) res.add(new LinkedList<>(path));
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.add(i);
            helper(k, n, sum, i + 1);
            sum -= i;
            path.removeLast();
        }
    }
}

3.电话号码的字母组合

力扣题目链接
看到此题就想到回溯的模板，首先一个问题是，数字和字母如何一一对应。
那就用一个数组来解决：

String[] numString = {
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "qprs",
    "tuv",
    "wxyz"
} //补了两个空字符为了补位，刚好从2开始

回溯三部曲

递归函数的参数及返回值

字符串s收集叶子节点的结果，然后字符串可变数组res保存。它俩为全局变量。
还需要index，它记录遍历到第几个数字了，就是题目中给出的digtis。

List<String> res = new ArrayList<>();
StringBuilder s = new StringBuilder();

private void helper(String digtis, int index){
}

确定终止条件

if (index == digtis.length()) {
  res.add(s);
  return;
}

确定单层遍历逻辑

通过index找到digtis中指向的数字，然后通过此数字找的numString中对应的字符集。

String str = numStirng[digtis.CharAt(index) - '0'];//减去字符0是为了转成int
for (int i = 0; i < str.length(); i++) {
    s.append(str.charAt(i));
    helper(digits, index + 1);
    s.deleteCharAt(s.length() - 1);
}

题解

class Solution {
    StringBuilder s = new StringBuilder();
    List<String> res = new ArrayList<>();

    String[] numString = {
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "qprs",
    "tuv",
    "wxyz"
};


    public List<String> letterCombinations(String digits) {
        if (digits.lenght() == 0) return res;
        helper(digits, 0);
        return res;

    }

    private void helper(String digits, int index) {
        if (index == digits.length()) {
            //开始写成res.add(s)报下面的错误
            // incompatible types: StringBuilder cannot be converted to String
            // res.add(s);

            res.add(s.toString());
            return;
        }
        // 通过index找digtis里的数字再从numString找这个数字对应的字符集
        String str = numString[digits.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++ ) {
            s.append(str.charAt(i));
            helper(digits, index + 1);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

小总结

第1、2、3题都是求组合的问题，但是有一些细节需要注意。
第1、2题是在同一个集合里面求组合，第3题是在不同的集合里求组合，也就是不同集合之间的组合。
for是横向遍历，递归是纵向遍历。

4.组合总和

力扣题目链接

同一个数字可以无限制重复被选取，总和等于target。

回溯三部曲

递归函数参数及返回值

两个全局变量，二维数组res存每一个结果，可变数组path存符合条件的结果。int型sum记录每一个path里面的总和。sum没有其实也可以，用target做减法也可以。int型index控制for循环横向遍历的起始位置。
如果是一个集合来求组合的话，就需要index。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用index。

List<List<Integer>> res = new LinkedList<>();
ArrayList<Integer> path = new ArrayList<>();

private void helper(int[] candidates, int target, int sum, int index) {
}

递归终止条件

sum大于target，return。
sum == target时，res收集结果，然后return。

if (sum > target) return;
if (sum == target) {
    res.add(new ArrayList<>(path));
    return;
}

单层遍历逻辑

for (int i = index; i < candidates.length; i++ ) {
  sum += candidates[i];
  path.add(candidates[i]);
  helper(candidates, target, sum, i);//注意：不是i+1，表示可以重复读取当前的数
  sum -= candidates[i];
  path.remove(candidates.length() - 1);
}

题解

```java

//在前面的分析中path和res使用全局变量来表示的，这里我们局部变量来表示

class Solution { public List> combinationSum(int[] candidates, int target) { List> res = new ArrayList<>(); Arraylist path = new ArrayList<>(); helper(candidates, target, res, path, 0, 0); return res;

}

private void helper(int[] candidates, int target, List<List<Integer>> res, ArrayList<Integer> path, int sum, int index) {
    if (sum == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    if (sum > target) return;

    for (int i = index; i < candidates.length; i++) {
        sum += candidates[i];
        path.add(candidates[i]);
        helper(candidates, target, res, path, sum, index); //这里不是i+1，表示可以重复
        sum -= candidates[i];
        path.remove(path.size() - 1);

    }
}

}

<a name="GCNIQ"></a>
### 5.组合总和II
[力扣题目链接](https://leetcode-cn.com/problems/combination-sum-ii/)<br />集合有重复的元素，但是不能有重复的组合。<br />横向遍历（for循环）不能出现重复的数字，纵向遍历（递归）可以出现重复的数字。<br />先对数组排序才可以去重。
<a name="ofPV1"></a>
#### 题解
```java
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, target, 0, 0);
        return res;

    }

    private void helper(int[] candidates, int target, int sum, int index) {
        if (sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }
        if (sum > target) return;

        for (int i =index; i < candidates.length; i++) {
            if (i > index && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            path.add(candidates[i]);
            helper(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.removeLast();
        }

    }

}

6.分割回文串

力扣题目链接
乍看上去，想到了

咋分割（之前都是一个个取）
咋判断回文子串

回溯三步法
递归函数及返回值

需要index，切割过的地方不能在切割。俩实例变量res和s

List<List<String>> res;
ArrayList<String> path;

private void helper(String s, int index){
}

终止条件pa

if (index >= s.size()) {
  res.add(new ArrayList<>(path));
  return;
}

单层搜素逻辑

for (int i = index; i < s.size(); i++) {
  if (isPalindrome(s, index, i)) {
      String str = s.substring(index, i + 1)；  //substr是左闭右开
      path.add(str);
  }else {
      continue;
  }

  helper(s, i + 1);
  path.removeLast();
}
/******************************判读是否为回文子串************************************/
//双指针法
private boolean isPalindrome(String s, int start, int end) {
  for (int i = start, j = end; i < j; i++, j--) {
      if (s.charAt(i) != s.charAt(j)) retuen false;
  }

  return true;
}

题解

class Solution {
  List<List<String>> res;
  LinkedList<String> path;
  public List<List<String>> partition(String s) {
      helper(s, 0);
      return res;

  }
  private void helper(String s, int index) {
      if (index >= s.length()) {
          res.add(path);
          return;
      }

      for (int i = index; i < s.length(); i++) {
          if (isPalindrome(s, index, i)) {
              String str = s.substring(index, i + 1);//substring是左闭右开的，所以+1
              path.add(str);

          } else {
              continue;
          }
          helper(s, i + 1);
          path.removeLast();
      }
  }

  private boolean isPalindrome(String s, int start, int end) {
  for (int i = start, j = end; i < j; i++, j--) {
      if (s.charAt(i) != s.charAt(j)) return false;
  }

  return true;
}
}

7.复原IP地址

力扣题目链接
截取子串并做判断，for循环里[index, i]这个区间就是截取的子串。

题解

class Solution {
  List<String> res = new ArrayList<>();
  LinkedList<String> path = new LinkedList<>();
  public List<String> restoreIpAddresses(String s) {
      helper(s, 0);
      return res;
  }

  private void helper(String s, int index) {
      if (path.size() == 4) {
          if (index == s.length()) {
              StringBuilder str = new StringBuilder();
              for (String seg : path) {
                  str.append(seg).append(".");
              }
              str.deleteCharAt(str.length() - 1);
              res.add(str.toString());
          }
          return;
      }

      for (int i = index; i < s.length(); i++) {
          String temp = s.substring(index, i + 1); //substring左闭右开，所以+1.
          if (Integer.parseInt(temp) > 255) return; 
          if (s.charAt(index) == '0' && index != i ) return;
          path.add(temp);
          helper(s, i + 1);
          path.removeLast();
      }
  }
}

8.子集问题

力扣题目链接
组合问题和切割问题都是收集树的叶子节点，而子集问题是找树所有的节点。

题解

class Solution {
  List<List<Integer>> res = new ArrayList<>();
  LinkedList<Integer> path = new LinkedList<>();

  public List<List<Integer>> subsets(int[] nums) {
      helper(nums, 0);
      return res;

  }

  private void helper(int[] nums, int index) {
      res.add(new ArrayList<>(path));//没有放在终止条件里面，每个节点都加到里面。而不是叶子节点才添加
      if (index > nums.length) return;

      for (int i = index; i < nums.length; i++) {
          path.add(nums[i]);
          helper(nums, i + 1);
          path.removeLast();
      }
  } 
}

9.子集II

第一：子集问题，收集每个节点的结果。res.add(new ArrayList<>(path))要写在递归函数的一开始。
第二：不能有有重复值。

要排序

if (index > i && nums[i] == nums[i - 1]) continue;

题解

class Solution {
  List<List<Integer>> res = new ArrayList<>();
  LinkedList<Integer> path = new LinkedList<>();

  public List<List<Integer>> subsetsWithDup(int[] nums) {
      Arrays.sort(nums);
      helper(nums, 0);
      return res;
  }
  private void helper(int[] nums, int index) {
      res.add(new ArrayList<>(path));

      if (index > nums.length) return;

      for (int i = index; i < nums.length; i++) {
          if (i > index && nums[i] == nums[i - 1]) continue;

          path.add(nums[i]);
          helper(nums, i + 1);
          path.removeLast();
      }
  }
}

10.递增子序列

这题一上来就踩坑了，去重时直接按之前的排序去重了。错了。
采用HashSet去重。
看力扣的题解时，对continue理解了。 ```java //path不为空且新的元素小于就得元素时（不是升序），进入下一次循环
for (int i = index; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {

  continue;

}
path.add(nums[i]);
helper(nums, i + 1);
path.removeLast();
}

//等价于上面的 for (int i = index; i < nums.length; i++) {
if (path.isEmpty() || nums[i] >= path.get(path.size() - 1)) { path.add(nums[i]);
helper(nums, i + 1);
path.removeLast();
}
}

<a name="wo2xr"></a>
#### 题解
```java
class Solution {
    Set<List<Integer>> res = new HashSet<>(); // 
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {

        helper(nums, 0);
        List<List<Integer>> ans = new ArrayList<>(res);
        return ans;
    }

    private void helper(int[] nums, int index) {
        if (path.size() >=2 ){ //至少两个元素，不能加return，因为要取每一个节点
            res.add(new ArrayList<>(path));
        }

       for (int i = index; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            path.add(nums[i]);
            helper(nums, i + 1);
            path.removeLast();
        }
    }
}

11.全排列

力扣题目链接

剩余集合里是除去使用元素后剩余的元素，和之前题目中剩余元素时index之后的元素是不一样的。
不用index这个参数了，但是需要used数组来记录哪个元素使用了，一个排列里面一个元素只能使用一次。

题解

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) return res;
        used = new boolean[nums.length];
        helper(nums);
        return res;
    }

    private void helper(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            path.add(nums[i]);
            used[i] = true;
            helper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

12.全排列 II

上一题的延伸，所给数组里面有重复的元素，要求返回不重复的全排列。
也就是多了一步最后结果去重的步骤，采用HashSet完成。

题解

class Solution {
    Set<List<Integer>> res = new HashSet<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        helper(nums);
        List<List<Integer>> ans = new ArrayList<>(res);
        return ans;
    }

    private void helper(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            path.add(nums[i]);
            used[i] = true;
            helper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

13.N皇后

力扣题目链接
for循环是列column方向的遍历，递归深度是行row控制的。

代表棋盘的二维数组要初始化
如何将二维数组转化为列表

皇后们的约束条件如何实现

题解

```java class Solution { List> res = new ArrayList<>();

public List> solveNQueens(int n) {

  char[][] board = new char[n][n];
  for (char[] seg : board){
      Arrays.fill(seg, '.');
  }
  backtrack(board, n, 0);
  return res;

}

private List charToList(char[][] board) {

  List<String> list = new ArrayList<>();
  for (char[] c : board) {
      list.add(String.copyValueOf(c));
  }
  return list;

}

private void backtrack(char[][] board, int n, int row) {

  if (row == board.length) {
      res.add(charToList(board));
      return;
  }

  for (int col = 0; col < n; col++) {
      if (isVaild(board, row, col, n)) {
          board[row][col] = 'Q';
          backtrack(board, n, row + 1);
          board[row][col] = '.';
      }
  }

}

private boolean isVaild(char[][] board, int row, int col, int n) {

  // 检查列是否有皇后冲突
  for (int i = 0; i < n; i++) {
      if (board[i][col] == 'Q') {
          return false;
      }
  }

  // 检查右上方是否有皇后冲突
  for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
      if (board[i][j] == 'Q') {
          return false;
      }
  }

  // 检查左上方是否有皇后冲突
  for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
          return false;
      }
  }
  return true;

}

} ```

14.解数独

力扣题目链接
没想出来，看了答案还是很迷。。。。。明天再看

回溯算法

回溯算法

回溯法一般解决的问题

回溯法的模板

LeetCode题目

1.组合

回溯三部曲

题解

2.组合总和 III

回溯三部曲

题解

3.电话号码的字母组合

回溯三部曲

题解

小总结

4.组合总和

回溯三部曲

题解

6.分割回文串

回溯三步法

题解

7.复原IP地址

题解

8.子集问题

题解

9.子集II

题解

10.递增子序列

11.全排列

题解

12.全排列 II

题解

13.N皇后

题解

14.解数独