回溯不适用于打印字符串的所有组合？

Question

我正在尝试打印字符串的所有排列。但是，尽管我尽了最大的努力，我还是无法获得我的代码所需的输出。有人可以解释我的代码有什么问题吗？我已经尝试了好几个小时，但惨遭失败。

以下代码的输出是：-

abc

这是回溯的置换函数：-

int i, l = 2;
void permute(String str, int n)
{
    for(i=n;i<=l;i++)
    {
        if(n==l)
        {
            System.out.println(swap(str,n,i));
            return;
        }
        else
            permute(swap(str,n,i),n+1);
    }
}

这是运行上面代码的主要函数：-

public static void main(String args[])
{
    BacktrackTest bt=new BacktrackTest();
    String c="abc";
    bt.permute(c,0);
}

这是交换代码：-

String swap(String st, int s1, int s2)
{
    char chr[] = st.toCharArray();
    char t;
    t = chr[s1];
    chr[s1] = chr[s2];
    chr[s2] = t;
    st = String.valueOf(chr);
    return st;
}

Answer 1

不要在 permute 方法之外定义 i。试试这个：

int l = 2;
void permute(String str, int n)
{
    for(int i=n;i<=l;i++)
    {
        if(n==l)
        {
            System.out.println(swap(str,n,i));
            return;
        }
        else
            permute(swap(str,n,i),n+1);
    }
}

如果您在 for 循环外声明 i，对于 return.
之后的调用者，它的值不是 "restored" 在您的示例中，当您输入 if(n==l) 时，i 的值是 2，但是在您 return; 之后它仍然是 2，因为它是全局范围的。所以在下一次迭代中它增加到 3，因此 i<=l 结果为假，程序结束。
如果你在循环内声明 i 它，在你 return; 之后它会回到 1 以便循环可以继续。

回溯不适用于打印字符串的所有组合？

Backtracking is not working for printing all combinations of a string?

java

dynamic-programming

backtracking

recursive-backtracking