java字谜算法

Question

我是这个论坛的新手，想问一个问题。我见过很多人问关于字谜的问题，但我的问题与这个特定的算法有关。我看到了这个算法，它使用递归技术生成字谜，但该算法的一部分对我来说不是很清楚。我想就采取这一具体步骤的原因寻求帮助。这个算法大纲是从编程面试中暴露出来的。以下是算法：

If you are past the last position
   print string and return
Otherwise
   For each letter in the input string
       If it is marked used, skip to the next letter
       Else place the letter in current position
   - Mark the letter used
   - Permute remaining letters staring at current position+1
   - Mark the letter as unused

以下是相同的代码：

void permute(String str){
    int length = str.length();
    boolean[] used = new boolean[length];
    StringBuffer out = new StringBuffer();
    char[] in = str.toCharArray();
    doPermute(in, out, used, length, 0);
}
void doPermute(char[] in, StringBuffer out, boolean[] used, int length,
    int level){
    if (level == length){
        System.out.println(out.toString());
        return;
    }
    for (int i = 0; i<length; i++){
        if (used[i]) continue;
        out.append(in[i]);
        used[i] = true;
        doPermute(in, out, used, length, level + 1);
        used[i] = false;
        out.setLength(out.length() - 1); // why are we reducing the size of out??
    }
}

代码解释中提到，当递归调用返回时，通过减小缓冲区大小，最后一个字符将被删除。我不明白为什么我们要删除最后一个字符？有人能给我指路吗。谢谢

Answer 1

恢复out.append(in[i]);（添加一个字符）的效果，并在每次迭代for循环后将缓冲区恢复到相同的状态

for (int i = 0; i<length; i++){
    if (used[i]) continue;
    out.append(in[i]); // try adding the ith letter
    used[i] = true;    // and mark it as used
    doPermute(in, out, used, length, level + 1); // do all the permutations for the remaining letters
    used[i] = false;                 // undo what we did
    out.setLength(out.length() - 1); // at the start of the loop
}

就这么简单