我在geeksforgeeks上看到过一段代码,用于使用递归和回溯来打印给定字符串的所有子序列,但我不明白回溯代码在for循环中是如何工作的。 请参见函数printSubSeq
class GFG
{
// str : Stores input string
// n : Length of str.
// curr : Stores current permutation
// index : Index in current permutation, curr
static void printSubSeqRec(String str, int n,
int index, String curr)
{
// base case
if (index == n)
{
return;
}
System.out.println(curr);
for (int i = index + 1; i < n; i++)
{
curr += str.charAt(i);
printSubSeqRec(str, n, i, curr);
// backtracking
curr = curr.substring(0, curr.length() - 1);
}
}
// Generates power set in
// lexicographic order.
static void printSubSeq(String str)
{
int index = -1;
String curr = "";
printSubSeqRec(str, str.length(), index, curr);
}
// Driver code
public static void main(String[] args)
{
String str = "cab";
printSubSeq(str);
}
}
输出为
c
ca
cab
cb
a
ab
b
谁给我解释一下这个密码。
如果我们在示例“cba”中工作,递归函数的第一次执行将递归地调用printSubSeqRec,在curr中添加“c”,索引增加1。
假设递归函数是正确的,我们期望递归调用打印字符串“ba”的所有子序列(因为我们将当前索引增加了1)。 所有这些子序列都将以我们添加到curr变量中的“c”开头。
这就是第一个子序列的打印方式,都以“C”开头:
c ca cab cb
在完成递归函数调用时,我们希望从curr变量中删除“c”,因为我们想要所有的子序列,而不仅仅是以“c”开头的子序列。
for循环的最后一行从curr中删除最后一个字符(在本例中,curr是删除“c”后的空字符串):
curr = curr.substring(0, curr.length() - 1);
并继续循环的下一次迭代(当前索引增加1),现在我们在空curr变量中添加“a”。 第二个递归调用将给我们的当前索引加1,curr=“a”它将打印从“b”开始的所有以“a”开头的子序列:
a ab
我希望这能帮助你更好的理解,我建议你从头到尾继续这个例子。