Проблемы рекурсивно порождающего подмножества

Question

Итак, алгоритм генерирует подмножества множества A, используя параметр i для ссылки на A [i], на каждом шаге происходит два вызова, один из которых включает A [i], а другой исключает A [i].Поиск останавливается, когда я == n.

Итак, это имеет смысл, но я не могу понять, что здесь делает последнее утверждение ..

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n){
        if (i==n) System.out.println(subset);
        else{
            search(i+1,subset,A,n);
            subset.add(A.get(i));
            search(i+1,subset,A,n);
            subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
        }
}

Я пытался исключить последнее утверждение, нозатем он повторяет элементы в подмножествах.Какая польза от последнего утверждения?

Answer 1

У вас есть единственный экземпляр subset на всех уровнях рекурсии.

Поэтому после использования элемента вы должны вернуться на более низкий уровень с тем же состоянием subset.

Представьте себе дерево вызовов

[]
     []
     [2]  *

[1]  
     [1]
     [1 2]

После того, как вы сделали подмножество [2] (кодовая точка *), вы возвращаетесь на первый уровень и должны сгенерировать подмножество [1].Но объект subset уже содержит элемент 2, поэтому создание [1] невозможно без удаления элемента 2 в *

---

Если реализация создает новую копию аргумента, вам не нужно восстанавливатьсостояние.