提问者:小点点

打印给定字符串的所有子序列


我在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

谁给我解释一下这个密码。


共1个答案

匿名用户

如果我们在示例“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

我希望这能帮助你更好的理解,我建议你从头到尾继续这个例子。