Рекурсия путаницы в списке

Question

Вот проблема

numberSet = [2,3,5], target number = 8
output -> [[2,2,2,2],[2,3,3],[3,5]]

И я думаю, что ее можно решить путем поиска с возвратом:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new LinkedList<>();
    permutation(candidates, target, new LinkedList(), result);
    return result;
}

public void permutation(int[] candidates, int target, List<Integer> subresult, List<List<Integer>> result){
    if(target == 0){
        result.add(subresult);
        return;
    }
    for(int x: candidates){
        if(target - x >= 0){
            subresult.add(x);
            permutation(candidates, target - x, subresult, result);
            subresult.remove(subresult.size() - 1);
        }
    }
        return;
}

Для меня все имеет смысл, однако мой результат:

[[],[],[],[]]

Все они пустой список ... Я хочу выяснить, почему я распечатываю каждый шаг, когда выполняется условие

if(target == 0){
        result.add(subresult);
        System.out.println(result);
        return;
    }

. И я думаю, что мой код действительно нашел решение (даже я не понял, как удалить эти дубликаты)

[[2, 2, 3]]
[[2, 3, 2], [2, 3, 2]]
[[3, 2, 2], [3, 2, 2], [3, 2, 2]]
[[7], [7], [7], [7]]

Почему это могло произойти ??? Почему список результатов все еще пуст? Огромное спасибо!

Answer 1

Ваш подход правильный, но поскольку вы удаляете последнее значение subresult- subresult.remove(subresult.size() - 1); при каждом вызове рекурсивного метода, и поскольку результат только добавляет ссылку на подрезультат, поэтому каждая операция добавления / удаления для подрезультатов будет также можно изменить в результате.

Короче -

Если подрезультат - [1,2,3] и вы добавляете его в результат, то result = [1,2,3]

Но теперь, если вы удалите 3 из подрезультатов, тогда результат также становится [1,2]

Итак, чтобы этого избежать,

result.add(new LinkedList<Integer>(subresult));

Это создает новый объект List со значениями из переданных в список.