java - 使用回溯算法排列字符串

Question

我在 Geeksforgeeks 上阅读了下面的代码，但我无法理解它是如何工作的!如果有人能形象地解释一下。那太好了!

这是代码:

static void swap(char a[], int l, int r) {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
}

static void permute(char a[], int l, int r) {
    if (l == r)
        System.out.println(getString(a));
    else {
        for (int i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i); // backtrack
        }
    }
}

Answer 1

我不明白你在哪里感到困惑:你提供了一张非常清楚地解释它的图片......给我。 :-)

终止条件(图表的底行，2 个红色和 1 个绿色项目):如果列表只剩下一个元素需要考虑，就没有地方可以交换它。排列完成。 返回

否则……对于数组中剩余的每个项目，将该位置交换到最左边的可用位置。将“固定”指针向右移动一位，并在数组的其余部分调用例程。

总的来说，这只是沿着数组走:(依次)选择每个项目作为第一个位置；第二个(依次)挑选每个剩余的项目； ... 继续到列表末尾。

这对你有什么帮助吗？