# Задача о сумме подмножеств

## Случай без повторяющихся элементов

!!! question

    Дан массив положительных целых чисел `nums` и целевое положительное целое число `target`. Найдите все возможные комбинации, сумма элементов которых равна `target`. В заданном массиве нет повторяющихся элементов, каждый элемент может быть выбран несколько раз. Верните эти комбинации в виде списка, в котором не должно быть повторяющихся комбинаций.

Например, для входного множества $\{3, 4, 5\}$ и целевого числа $9$ решениями будут $\{3, 3, 3\}, \{4, 5\}$. Следует обратить внимание на следующие два момента:

- элементы входного множества можно выбирать неограниченное количество раз;
- порядок элементов в подмножестве не имеет значения, например $\{4, 5\}$ и $\{5, 4\}$ — одно и то же подмножество.

### Сравнение с решением задачи о полных перестановках

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

Однако, в отличие от задачи о полных перестановках, **в данной задаче элементы множества можно выбирать неограниченное количество раз**, поэтому нет необходимости использовать булев список `selected` для записи выбранных элементов. Для получения начального решения можно просто немного изменить код для полных перестановок.

```src
[file]{subset_sum_i_naive}-[class]{}-[func]{subset_sum_i_naive}
```

При вводе в этот код массива $[3, 4, 5]$ и целевого элемента $9$ будет выведено $[3, 3, 3], [4, 5], [5, 4]$. **Хотя удалось найти все подмножества с суммой $9$, среди них есть повторяющиеся подмножества $[4, 5]$ и $[5, 4]$**.

Это происходит потому, что процесс поиска различает порядок выбора, тогда как в подмножествах порядок элементов не важен. Как показано на рисунке ниже, сначала выбрать $4$, а затем $5$ и сначала выбрать $5$, а затем $4$ — это разные ветви, но они соответствуют одному и тому же подмножеству.

![Поиск подмножеств и обрезка по превышению целевого значения](subset_sum_problem.assets/subset_sum_i_naive.png)

**Одним из очевидных подходов к устранению повторяющихся подмножеств является удаление дубликатов из списка результатов**. Однако этот метод очень неэффективен по двум причинам:

- Когда в массиве много элементов, особенно когда значение `target` велико, процесс поиска генерирует множество повторяющихся подмножеств.
- Сравнение подмножеств (массивов) на различия — очень затратная по времени операция. Она требует сначала сортировки массивов, затем сравнения различий каждого элемента в массиве.

### Обрезка повторяющихся подмножеств

**Рассмотрим устранение дубликатов в процессе поиска с помощью обрезки**. На рисунке ниже показано, что повторяющиеся подмножества возникают при выборе элементов массива в разном порядке, например в следующих случаях:

1. Пусть на первом и втором этапах выбираются $3$ и $4$ соответственно, создаются все подмножества, содержащие эти два элемента, обозначенные как $[3, 4, \dots]$.
2. Затем если на первом этапе выбирается $4$, **то на втором этапе следует пропустить $3$**, так как подмножество $[4, 3, \dots]$ полностью повторяет подмножество, созданное на этапе `1.`.

В процессе поиска выбор на каждом уровне осуществляется слева направо. Поэтому чем правее ветвь, тем больше она обрезается.

1. На первых двух этапах выбираются $3$ и $5$ и создаются подмножества $[3, 5, \dots]$.
2. На первых двух этапах выбираются $4$ и $5$ и создаются подмножества $[4, 5, \dots]$.
3. Если на первом этапе выбирается $5$, **то на втором этапе следует пропустить $3$ и $4$**, так как подмножества $[5, 3, \dots]$ и $[5, 4, \dots]$ полностью повторяют подмножества, описанные на этапах `1.` и `2.`.

![Повторяющиеся подмножества, полученные в результате различного порядка выбора](subset_sum_problem.assets/subset_sum_i_pruning.png)

Обобщим эту мысль. Пусть задан входной массив $[x_1, x_2, \dots, x_n]$. Тогда в процессе поиска последовательность выбора $[x_{i_1}, x_{i_2}, \dots, x_{i_m}]$ должна удовлетворять условию $i_1 \leq i_2 \leq \dots \leq i_m$, **в противном случае она приведет к дубликатам, и ее нужно обрезать**.

### Код реализации

Для реализации этой обрезки мы инициализируем переменную `start`, которая указывает начальную точку обхода. **После выбора $x_{i}$ следующая итерация начинается с индекса $i$**. Это позволяет для последовательности выбора соблюдать условие $i_1 \leq i_2 \leq \dots \leq i_m$, обеспечивая уникальность подмножеств.

Кроме того, в код были внесены следующие две оптимизации:

- Перед началом поиска массив `nums` сортируется. При обходе всех вариантов, **если сумма подмножества превышает `target`, цикл завершается**, так как последующие элементы больше, и их сумма также превысит `target`.
- Исключение переменной `total`, **подсчет суммы элементов осуществляется с помощью вычитания из `target`**. Решение фиксируется, когда `target` равен $0$.

```src
[file]{subset_sum_i}-[class]{}-[func]{subset_sum_i}
```

На рисунке ниже показан полный процесс поиска с возвратом для массива $[3, 4, 5]$ и целевого элемента $9$.

![Процесс поиска с возвратом для реализации задачи о сумме подмножеств I](subset_sum_problem.assets/subset_sum_i.png)

## Случай с повторяющимися элементами

!!! question

    Дан массив положительных целых чисел `nums` и целевое положительное целое число `target`. Найдите все возможные комбинации, сумма элементов которых равна `target`. **Заданный массив может содержать повторяющиеся элементы, каждый элемент может быть выбран только один раз**. Верните эти комбинации в виде списка, в котором не должно быть повторяющихся комбинаций.

В отличие от предыдущей задачи **входной массив может содержать повторяющиеся элементы**, что создает новую проблему. Например, для массива $[4, \hat{4}, 5]$ и целевого элемента $9$ текущий код выдает результат $[4, 5], [\hat{4}, 5]$, что приводит к повторяющимся подмножествам.

**Причина этих повторов в том, что равные элементы выбираются несколько раз на одном этапе**. На рисунке ниже показано, что на первом этапе есть три варианта выбора, два из которых равны $4$. Это приводит к двум повторяющимся ветвям поиска и, следовательно, к повторяющимся подмножествам. Аналогично два элемента $4$ на втором этапе также создают повторяющиеся подмножества.

![Повторяющиеся подмножества из-за равных элементов](subset_sum_problem.assets/subset_sum_ii_repeat.png)

### Обрезка равных элементов

Для решения этой проблемы **необходимо сделать выбор равных элементов на каждом этапе однократным**. Реализация этого подхода довольно изящна: поскольку массив отсортирован, равные элементы находятся рядом друг с другом. Это означает, что если текущий элемент равен предыдущему, то он уже был выбран, и его следует пропустить.

В то же время **в этой задаче предусмотрено, что каждый элемент массива может быть выбран только один раз**. К счастью, можно использовать переменную `start` для выполнения этого ограничения: после выбора $x_{i}$ начинаем следующий цикл с индекса $i + 1$. Это позволяет исключить повторяющиеся подмножества и избежать повторного выбора элементов.

### Код реализации

```src
[file]{subset_sum_ii}-[class]{}-[func]{subset_sum_ii}
```

На рисунке ниже демонстрируется процесс обратного отслеживания для массива $[4, 4, 5]$ и целевого элемента $9$, включающий четыре вида обрезки. Проанализируйте рисунок и комментарии в коде, чтобы лучше понять весь процесс поиска и как работают различные операции обрезки.

![Процесс поиска с возвратом для реализации задачи о сумме подмножеств II](subset_sum_problem.assets/subset_sum_ii.png)