Как правильно вернуть ArrayList <Object>из рекурсивного метода без повторяющихся значений?

Question

Мне нужно рекурсивное решение, которое возвращает любую комбинацию из n подмножеств из набора k (в математическом смысле). У меня есть ArrayList, и я хочу вернуть любые возможные подмножества n-размера из рекурсивного метода. Заказ не имеет значения. Поэтому, если у меня есть набор сотрудников {Джим, Том, Энн, Джон} и я хочу 2 из них, я должен получить:

{Джим Том} {Джим Энн} {Джим Джон} {Том Энн} {Том Джон} {Энн Джон}

Я нашел это https://stackoverflow.com/a/16256122/10929764 но это только распечатывает результат. Я немного изменил его, чтобы добавить любую комбинацию в ArrayList и вернуть ее, но она не работает должным образом. Вот код:

    public ArrayList<Employee[]> combinationsOfEmployee(ArrayList<Employee>sourceList, int selected, int startIndex, Employee[] result, ArrayList<Employee[]>allResults){
        if(selected == 0){
            for(int i=0; i<result.length; i++){
                System.out.print(result[i].getLastName() + "  ");
            }
            System.out.println("");
            allResults.add(result);
            return allResults;
        }
        for(int i=startIndex; i<=sourceList.size() - selected; i++){
            result[result.length - selected] = sourceList.get(i);
            combinationsOfEmployee(sourceList, selected - 1, i + 1, result, allResults);
        }
        return allResults;
    }

Он правильно распечатывает все комбинации, но постоянно добавляет одни и те же значения в ArrayList. Так что allResults это

{Энн, Джон} {Энн, Джон} {Энн, Джон} {Энн, Джон} {Энн, Джон} {Энн, Джон}

вместо:

{Джим Том} {Джим Энн} {Джим Джон} {Том Энн} {Том Джон} {Энн Джон}

Answer 1

Вы задаетесь вопросом, почему он печатает это нормально, в то время как возвращаемый список, кажется, имеет точно такой же массив в каждой позиции.
Это потому, что это точно такой же массив (та же ссылка на тот же объект). Поскольку в вашем решении вы используете только один массив, при вызове allResults.add(result) вы добавляете ссылку на ваш единственный массив в списке. Затем вы продолжаете изменять его, когда вы ищете другие комбинации. Вот почему ваш список содержит только последнюю найденную комбинацию.

Решением этой проблемы является добавление нового массива каждый раз, когда вы находите комбинацию, путем добавления копии вашего текущего массива в список. Просто замените

allResults.add(result);

по

allResults.add(Arrays.copyOf(result, result.length));

Таким образом, каждый элемент вашего списка указывает на отдельный массив.