递归，每一步导出信息

Question

我正在编写输出字符串数组所有组合的代码。我可以使用 doCombine 方法打印一个数组，但是当要将该数组添加到 LinkedList 时，它会添加仅包含 D 的数组。如何将每个数组传递到我的列表？

public LinkedList<String[]> allCombinations = new LinkedList<String[]>();

public static void main(String[] args) {
    String[] arr = {"A", "B", "C", "D"};

    Combinations c = new Combinations();

    c.combine(arr, 0);
    c.combine(arr, 1);
    c.combine(arr, 2);
    c.combine(arr, 3);
    c.combine(arr, 4);
    c.printList();

}

private void combine(String[] arr, int r) {
    String[] res = new String[r];
    doCombine(arr, res, 0, 0, r);
}

private void doCombine(String[] arr, String[] res, int currIndex, int level, int r) {
    if (level == r) {

        printArray(res);
        //Here it doesn't work
        allCombinations.add(res);
        return;
    }
    for (int i = currIndex; i < arr.length; i++) {
        res[level] = arr[i];
        doCombine(arr, res, i + 1, level + 1, r);

        if (i < arr.length - 1 && arr[i].equals(arr[i + 1])) {
            i++;
        }
    }
}

private void printArray(String[] res) {

    for (int i = 0; i < res.length; i++) {
        System.out.print(res[i] + " ");
    }
    System.out.println();
}

public void printList() {
    for (int i = 0; i < allCombinations.size(); i++) {
        printArray(allCombinations.get(i));
    }

}

Answer 1

我假设 allCombinations 是 List<String[]>（链表）的实现。

我认为你的错误是当你做allCombinations.add(res)时，你在你的List中添加了对对象res的引用，但是这个对象在[=16]之后被修改了=].

因此，当您在 add 之前打印 res 时，您打印的是当前值，但是，在列表中，您有 N 个对同一对象的引用 res 结束成为一系列 'D'（当你打印列表时，你打印 N 次 res 的最后一个值）

添加时必须克隆列表的当前值，它会起作用：

private void doCombine(String[] arr, String[] res, int currIndex, int level, int r) {
    if (level == r) {

        printArray(res);
        //Here it doesn't work
        allCombinations.add(res.clone());
        return;
    }
    for (int i = currIndex; i < arr.length; i++) {
        res[level] = arr[i];
        doCombine(arr, res, i + 1, level + 1, r);

        if (i < arr.length - 1 && arr[i].equals(arr[i + 1])) {
            i++;
        }
    }
}

递归，每一步导出信息

Recursives, exporting info at each step

java

arrays

recursion

combinations

linked-list