递归与回溯入门疑问：字典序幂集代码的回溯执行逻辑

问题背景 #

刚接触递归与回溯，搞不懂以下生成字典序幂集的Java代码中for循环内递归调用后的执行逻辑，尤其是回溯操作的具体运行机制。

代码实现 #

import java.util.Arrays;

class Solution {

// str : 存储输入字符串
// n : str的长度
// curr : 存储当前生成的子集
// index : 当前子集在原字符串中的最后一个字符的索引
static void permuteRec(String str, int n,
                       int index, String curr)
{
    // 基准条件：当索引等于字符串长度时，直接返回
    if (index == n) {
        return;
    }
    System.out.println(curr);
    for (int i = index + 1; i < n; i++) {

        // 将当前字符加入到当前子集
        curr += str.charAt(i);
        // 递归生成后续子集
        permuteRec(str, n, i, curr);

        // 回溯操作：移除刚加入的字符，恢复到之前的状态
        curr = curr.substring(0, curr.length() - 1);
    }
    return;
}

// 按字典序生成幂集
static void powerSet(String str)
{
    char[] arr = str.toCharArray();
    Arrays.sort(arr);
    permuteRec(new String(arr), str.length(), -1, "");
}

// 测试代码
public static void main(String[] args)
{
    String str = "abc";
    powerSet(str);
}
}

输出结果 #

a ab b c ca cab cb 

（注：实际代码执行会先打印空字符串，此处输出可能存在粘贴遗漏）

核心逻辑解析 #

1. 整体流程

这段代码通过递归+回溯的方式生成字典序幂集：

• 先对输入字符串排序，保证后续生成的子集按字典序排列；
• 从空集开始，每次选择原字符串中当前索引之后的字符加入当前子集，递归处理后续字符；
• 递归返回后，通过回溯操作撤销刚才的选择，尝试下一个可能的字符。

2. 回溯操作的运行机制

回溯的核心是恢复状态，让程序回到选择某个字符之前的状态，从而能遍历所有可能的子集分支。我们以输入abc为例，一步步拆解关键步骤：

第一步：初始调用

permuteRec("abc", 3, -1, "")

• 不触发基准条件，先打印空字符串；
• 进入for循环，i从0开始（index+1 = -1+1=0）：
  • curr变为"a"；
  • 递归调用permuteRec("abc", 3, 0, "a")。

第二步：递归处理"a"的分支

permuteRec("abc", 3, 0, "a")

• 打印"a"；
• 进入for循环，i从1开始：
  • curr变为"ab"；
  • 递归调用permuteRec("abc", 3, 1, "ab")。

第三步：递归处理"ab"的分支

permuteRec("abc", 3, 1, "ab")

• 打印"ab"；
• 进入for循环，i从2开始：
  • curr变为"abc"；
  • 递归调用permuteRec("abc", 3, 2, "abc")。

第四步：递归到最深层

permuteRec("abc", 3, 2, "abc")

• 打印"abc"；
• for循环中i=3，不满足i<3，循环结束，直接返回。

第五步：第一次回溯

回到permuteRec("abc", 3, 1, "ab")的for循环中，执行curr = curr.substring(0, curr.length()-1)：

• curr从"abc"变回"ab"；
• 循环结束，返回上一层。

第六步：第二次回溯

回到permuteRec("abc", 3, 0, "a")的for循环中，执行回溯：

• curr从"ab"变回"a"；
• 继续循环，i=2：
  • curr变为"ac"；
  • 递归调用permuteRec("abc",3,2,"ac")，打印"ac"后返回；
  • 回溯，curr变回"a"；
• 循环结束，返回上一层。

第七步：第三次回溯

回到初始调用的for循环中，执行回溯：

• curr从"a"变回""；
• 继续循环，i=1，生成"b"相关的所有子集；
• 接着i=2，生成"c"相关的所有子集。

3. 为什么需要回溯？

如果没有回溯操作，curr会一直累加字符，无法回到之前的状态去尝试其他分支。比如在生成"ab"之后，必须把'b'移除，才能回到"a"的状态，进而生成"ac"；同理，生成完"a"相关的所有子集后，必须把'a'移除，才能回到空集状态，生成"b"、"c"相关的子集。

内容的提问来源于stack exchange，提问作者Bodhisattwa Basu