组合问题

问题描述

给定一个无重复元素的数组num和一整数m，返回所有可能的m个数的组合。

代码实现

咱们的目标是用深度优先搜索（DFS）配合回溯策略，来找出所有可能的数字组合。

combination 方法都干了啥:

准备一个result列表: 这个列表 (List<List<Integer>>) 用来装所有找出来的组合。每个组合它自己也是一个整数列表。
再准备一个path列表: 这个列表 (List<Integer>) 临时记录咱们在DFS过程中，当前正在凑的这个组合长啥样。
调用dfs干活: dfs是真正干搜索和凑组合的递归函数。
- num: 就是输入的那个原始数组。
- m: 咱们要凑的组合里有几个数。
- 0: 从数组的第0个位置开始选数。
- path: 当前凑到一半的组合。
- result: 最终装结果的那个列表。
返回result: 等dfs跑完了，result里面就装满了所有大小为m的组合，把它返回就行。

dfs (深度优先搜索) 是回溯算法的精髓所在。

啥时候停呢？（递归的出口）:
- if(path.size()==m): 如果当前path列表里的数字个数，正好等于咱们想要的组合大小m，那说明一个组合凑齐了。
- result.add(new ArrayList<Integer>(path)): 赶紧把这个凑好的path存到result里。特别注意：这里一定要 new ArrayList<>(path) 创建一个新的列表再存进去。为啥呢？因为path这个列表在后面的回溯步骤里还会被修改（删掉元素）。如果不创建副本，那result里存的所有组合都会指向同一个不断变化的path对象，最后结果就全乱套了。
- return;: 找到了一个组合，这条递归的路就走到头了，返回。
递归探索和"反悔"（回溯）的过程:
- for(int i=start; i<num.length; i++): 这个循环呢，就是从数组num的start位置开始，一个一个往后看。start参数有啥用？
  - 它保证在凑一个组合的时候，同一个数字不会被重复用。
  - 它还能避免生成重复的组合。打个比方，如果我们已经考虑过以num[0]开头的组合了，那后面选数的时候，就没必要再回头去选num[0]之前的数来凑新组合了。因为那样凑出来的组合，只是顺序不一样（比如[1,2]和[2,1]，假设原数组是[1,2,3,...]），但组合本身是不讲究元素顺序的。
- path.add(num[i]): 做选择：先把当前看到的num[i]这个数加到path里，表示"我选它了！"。
- dfs(num, m, i+1, path, result): 继续往下走：递归调用dfs，让它接着凑。
  - 这里的i+1是关键！它告诉下一层dfs：“你从我选的这个num[i]的下一个位置开始选数吧。” 这样做能确保组合里的数是按原数组里的顺序（或者说，索引是递增的）选出来的，自然也就避免了像[1,2]和[2,1]这样的重复组合。
- path.remove(path.size()-1): 反悔操作（回溯）：当上面那行dfs调用结束返回了，说明从num[i]开始、包含m个数的所有组合都已经找遍了。这时候，就得把刚才加入path的num[i]给删掉。这个操作就像是"撤销"了刚才的选择，程序退回到选num[i]之前的状态。这样，for循环的下一次迭代（i++）才能去尝试选num[i]后面的其他数字，从而探索其他的组合可能性。

举个例子看看咋工作的: 假设 num = [1, 2, 3], m = 2。

combination([1,2,3], 2) 会调用 dfs([1,2,3], 2, 0, [], result)。
dfs(start=0):
- i=0 (选元素 1):
  - path.add(1)，现在 path = [1]
  - 调用 dfs([1,2,3], 2, 1, [1], result)
    - dfs(start=1):
      - i=1 (选元素 2):
        
        path.add(2)，现在 path = [1, 2]
        
        path.size() == m (2 == 2) 满足，于是 result.add([1,2])。这条路结束，返回。
        
        path.removeLast()，path 变回 [1] (回溯)
      - i=2 (选元素 3):
        
        path.add(3)，现在 path = [1, 3]
        
        path.size() == m (2 == 2) 满足，于是 result.add([1,3])。这条路结束，返回。
        
        path.removeLast()，path 变回 [1] (回溯)
      - i 到头了 (i=2 是最后一个可选的)。dfs(start=1)结束，返回。
  - path.removeLast()，path 变回 [] (回溯)
- i=1 (选元素 2):
  - path.add(2)，现在 path = [2]
  - 调用 dfs([1,2,3], 2, 2, [2], result)
    - dfs(start=2):
      - i=2 (选元素 3):
        
        path.add(3)，现在 path = [2, 3]
        
        path.size() == m (2 == 2) 满足，于是 result.add([2,3])。这条路结束，返回。
        
        path.removeLast()，path 变回 [2] (回溯)
      - i 到头了。dfs(start=2)结束，返回。
  - path.removeLast()，path 变回 [] (回溯)
- i=2 (选元素 3):
  - path.add(3)，现在 path = [3]
  - 调用 dfs([1,2,3], 2, 3, [3], result)
    - dfs(start=3):
      - path.size() (1) 不等于 m (2)。
      - for 循环条件 i < num.length (3 < 3) 不满足，循环不执行。dfs(start=3)结束，返回。
  - path.removeLast()，path 变回 [] (回溯)
- i 到头了。dfs(start=0)结束，返回。
combination 方法返回 result，里面装着 [[1,2], [1,3], [2,3]]。

 1// 组合
 2public static List<List<Integer>> combination(int[] num, int m){
 3    List<List<Integer>> result = new ArrayList<>();
 4    List<Integer> path = new ArrayList<>();
 5    dfs(num,m,0,path,result);
 6    
 7    return result;
 8    
 9}
10
11// 深度优先搜索
12public static void dfs(int[] num, int m, int start, List<Integer> path, List<List<Integer>> result) {
13    if(path.size()==m) {
14        result.add(new ArrayList<Integer>(path));
15        return;
16    }
17    
18    for(int i=start;i<num.length;i++) {
19        path.add(num[i]);
20        dfs(num, m, i+1, path, result);
21        path.remove(path.size()-1);
22    }
23}

复杂度分析

时间复杂度：$O(C(n,m)\cdot m)$
空间复杂度：$O(m)$

排列问题

问题描述

给定一个无重复元素的数组num和一整数m，返回所有可能的m个数的排列。

代码实现

这里与组合数不同，我们不需要start参数，因为排列问题中，每个位置的元素都可以是任意一个未被选过的元素。作为替代，我们使用一个visited数组来跟踪每个元素是否已经被使用过。

主要的步骤和组合数一样，都是先在path中添加元素，然后递归调用backtrack，最后回溯，从path中删除元素。不过注意在添加元素前，先把visited数组中对应的元素设置为true，表示这个元素已经被使用过，然后回溯时再把它设置为false，表示这个元素没有被使用过。

 1// 排列
 2public static List<List<Integer>> permutation(int[] num, int m){
 3    boolean[] visited = new boolean[num.length];
 4    List<Integer> path = new ArrayList<>();
 5    List<List<Integer>> result = new ArrayList<>();
 6    backtrack(num,m,visited,path,result);
 7    return result;
 8}
 9
10// 回溯
11public static void backtrack(int[] num, int m, boolean[] visited, List<Integer> path, List<List<Integer>> result) {
12    if(m==path.size()) {
13        result.add(new ArrayList<>(path));
14        return;
15    }
16    for(int i=0;i<num.length;i++) {
17        if(visited[i]) continue;
18        visited[i] = true;
19        path.add(num[i]);
20        backtrack(num, m, visited, path, result);
21        path.remove(path.size()-1);
22        visited[i] = false;
23    }
24}

复杂度分析

时间复杂度：$O(P(n,m)\cdot m)$
空间复杂度：$O(m)$

经典例题：分割回文串

问题描述

给定一个字符串s，返回所有可能的分割方式，使得每个子串都是回文串。这里认为单个字符也是回文串。

代码实现

这个问题咱们同样用回溯法（或者叫深度优先搜索，DFS）来解决。目标就是把一个字符串 s 切割成好几段，而且每一段都必须是个回文串。回溯算法呢，就是通过在字符串的不同位置尝试"剪一刀"，来找出所有可能的切割方案。

主要的思路是这样的：

想象咱们现在站在字符串的某个位置 start。
从这个 start 位置开始，往后瞅，试试切下来一段子串。
看看切下来的这段子串是不是回文的。
要是回文的，太好了！把它记到咱们当前的路径 path 里。然后呢？对剩下还没切的那部分字符串，从刚才切完的地方往后，重复一样的操作。
等从更深一层的探索回来之后，就得"反悔"一下，把刚才记到 path 里的那段子串删掉。这样才能试试别的切法，比如从同一个 start 位置开始，切一个更长点的回文串出来。

下面来看看 dfs 函数和它的小助手 isPalindrome 是怎么干活的：

dfs(String s, int start, List<String> path, List<List<String>> results) 这个函数是核心：
- s：就是咱们要切的那个原字符串。
- start：这是个数字，告诉我们当前要从字符串 s 的第几个字符开始找下一段回文子串。
- path：一个临时的 List<String>，像个小本本，记录着咱们当前这一趟切下来的一串回文子串是哪些。
- results：一个 List<List<String>>，这是最终的成果篮子，所有成功的切法（每一套切法都是一个回文子串列表）都会装到这里面。
啥时候算切完了呢？（递归的出口）：
- 当 start 这个数字等于字符串 s 的总长度 s.length() 的时候，就说明咱们已经从头到尾把整个字符串 s 都成功切成了回文串啦！
- 这时候，path 小本本里记的就是一套完整的、成功的切割方案。赶紧把它存到 results 成果篮子里。特别注意：这里一定要 new ArrayList<>(path) 创建一个新的列表再存进去。为啥呢？因为path这个小本本在后面的回溯步骤里还会被修改（删掉里面的子串）。如果不创建副本，那results里存的所有方案都会指向同一个不断变化的path对象，最后结果就全乱套了。
探索和"反悔"（回溯）的过程是咋样的：
- 函数里有个 for 循环，它会从当前的 start 位置开始，一直到字符串末尾，尝试所有可能的切割点 i。
- 对于每一个可能的切割点 i，咱们就先切出一段子串 substr = s.substring(start, i + 1)。这段 substr 就是从当前 start 位置开始，到 i 位置（包括 i 本身）结束的这么一段。
- 第一步，判断一下是不是回文：喊小助手 isPalindrome(substr) 来帮忙看看这段 substr 是不是个回文串。
- 如果 substr 确实是回文串，那接下来：
  - 做选择 (选它！)：把它加到咱们的 path 小本本里：path.add(substr)。
  - 继续往下切 (深入探索)：递归调用 dfs(s, i + 1, path, results)。注意，新的起始点变成了 i + 1，因为 substr 已经把从 start 到 i 这些字符给占了，下一次就从 i 的下一个位置开始切。
  - 反悔操作 (撤销选择/回溯)：当上面那行 dfs 调用结束返回了，说明基于当前这个 substr 开头的所有后续切法都已经试完了。为了能试试其他的可能性（比如，从同一个 start 位置开始，尝试切一个更长的回文子串；或者，在更早的切割步骤里，选择一个不一样的初始子串），咱们就得把刚才加入 path 的那个 substr 给删掉：path.remove(path.size() - 1)。这个操作就像是"撤销"了刚才的选择，程序退回到选 substr 之前的状态。
isPalindrome(String s)：
- 这个函数很简单，就是专门判断一个字符串 s 是不是回文的。
- 我们用"双指针"的方法：一个指针指着字符串的开头，另一个指着字符串的末尾。两个指针同时往中间跑，一边跑一边比较它们指着的字符是不是一样。如果跑到中间或者相遇了，所有对应位置的字符都一样，那这个字符串就是回文的。
- （题目通常会说，空字符串或单个字符的串也算回文——代码里也通常会处理这种情况）。

通过这种"一路切下去，不合适就退回来换条路再切"的深度优先搜索和回溯机制，这个算法就能把所有可能的切割方式都系统地试一遍，然后把那些每一段都是回文串的成功方案都收集起来。

 1public static List<List<String>> divide(String s){
 2    List<String> path = new ArrayList<>();
 3    List<List<String>> results = new ArrayList<>();
 4    dfs(s, 0, path, results);
 5    return results;
 6}
 7
 8public static void dfs(String s, int start, List<String> path, List<List<String>> results) {
 9    if(start == s.length()) { // 此时start应该已经移到字符串末字符的下一个位置了，所以不是length-1
10        results.add(new ArrayList<>(path)); // 必须添加一个副本而不是引用本身
11    }
12            
13    for(int i=start;i<s.length();i++) {
14        String substr = s.substring(start, i+1);
15        if(isPalindrome(substr)) {
16            path.add(substr);
17            dfs(s, i+1, path, results);
18            path.remove(path.size()-1);
19        }
20    }
21    
22    
23}
24
25public static boolean isPalindrome(String s) {
26    // 空字符串
27    if (s == null || s.length() == 0) {
28            return true; 
29    }
30    int start = 0, end = s.length() - 1;
31    while (start < end) {
32        if (s.charAt(start) != s.charAt(end)) {
33            return false;
34        }
35        start++;
36        end--;
37    }
38    return true;
39}

复杂度分析

时间复杂度：通常$O(2^n)$
空间复杂度：$O(n)$、$O(n^2)$，取决于字符串的存储方式

dfs回溯

dfs回溯问题：组合问题、排列问题、回文子串分割的所有方案

组合问题

问题描述

代码实现

复杂度分析

排列问题

问题描述

代码实现

复杂度分析

经典例题：分割回文串

问题描述

代码实现

复杂度分析