algorithm - 没有得到正确的预期输出

Question

给定一个数字 d 和一个数字 n。 我必须打印所有长度 n 的组合，这样第一个元素是 d 并且所有其他元素都是 与前一个相距 1 个距离。

例如对于输入 d=4 n=3

输出

4 3 2 4 3 4 4 5 4 4 5 6

我写了下面的代码，但它每行显示两次如下 -

4 3 2 4 3 2 4 3 4 4 3 4 4 5 4 4 5 4 4 5 6 4 5 6

代码-

private static void printNumbers(int d, int n, String comb) {
    if(n == 0) {
        System.out.println(comb);
        return;
    }

    printNumbers(d-1, n-1, comb+d+"\t");
    printNumbers(d+1, n-1, comb+d+"\t");
}

方法调用看起来像 -

 printNumbers(4,3,"");

我尝试调试但无法提出没有重复输出的测试条件。 我知道我们可以使用 Set 或类似的 DS 来避免重复，但我想知道是否有不使用额外空间的解决方案。

Answer 1

你的问题是，当 n == 1 时，你调用:

printNumbers(d-1, 0, comb+d+"\t");
printNumbers(d+1, 0, comb+d+"\t");

这将打印字符串两次。

您可以通过更改停止标准轻松解决此问题:

private static void printNumbers(int d, int n, String comb) {
    if(n == 1) {
    //      ^ change here
        System.out.println(comb + d);
        //                      ^ change here
        return;
    }

    printNumbers(d-1, n-1, comb+d+"\t");
    printNumbers(d+1, n-1, comb+d+"\t");
}