Блог

Итак, алгоритм генерирует подмножества множества A, используя параметр i для ссылки на A[i], на каждом шаге выполняется два вызова, один из которых включает A [i], а другой исключает A [i]. Поиск прекращается, когда 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*/
        }
}
  

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

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

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

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

 []
     []
     [2]  *

[1]  
     [1]
     [1 2]
  

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

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