Как найти все возможные суммы числа

Как то так, это по поводу » Чтобы использовалось не только два значения»

import itertools


def summs(answer, *dig):

    res = []
    for i in range(1, answer + 1):
        for j in itertools.combinations_with_replacement(list(dig), i):
            if sum(list(j)) == answer:
                res.append(j)
    return res


print(summs(13, *range(1, 11)))

Результат:

[(3, 10), (4, 9), (5, 8), (6, 7), (1, 2, 10), (1, 3, 9), (1, 4, 8), (1, 5, 7), (1, 6, 6), (2, 2, 9), (2, 3, 8), (2, 4, 7)... и тд

Время на прочтение
8 мин

Количество просмотров 4.8K

Доброго всем дня, меня вдохновила статья «Всё, что вы хотели знать о динамическом программировании, но боялись спросить», за что Вам огромное спасибо.

Приоритет нашей задачи: минимизация времени выполнения поиска, так как полная проверка уходит в арифметическую прогрессию.

Где я использую этот модуль? Мне была поставлена задача распределения разносортного товара на паллеты, «1» это метр кубический — объем помещающийся на паллет. У меня была мысль раскидать по объему товар 0,25 / 0,5 / 0,75 и логически складывать, 0,5 +0,5 / 0,75 + 0,25, но это породило огромное количество когда , чем дальше, тем сложнее это было.

Для моей задачи выходом стала «Ленивая динамика:» из вышеуказанной статьи.

В этом примере из статьи идет последовательное сложение строк и перебор в цикле с какого элемента начинать сложение — перебор вариантов сложения.

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

Это рабочий код из моей программы, отлаженный.

Таблица000//(Таблица Значений с товаром), 
Эдиал = 1; //=1 метру кубическому	
КоличествоСтрокТаб = Таблица000.Количество();//количество строк	

ОтклонениеВПлюс =Число("0,1");//до 1,1
ОтклонениеВМинус = Число("0,1");//до 0,9
ОптимальнаяРазница = Эдиал;//задаем максимальную разницу
	ОптимальнаяСумма = 0;
//задаем 2 табличные части или можно использовать массивы, по вкусу
	ОптимальнаяТаблицаСтрок = Новый ТаблицаЗначений;     
    ОптимальнаяТаблицаСтрок.Колонки.Добавить("НомерСтрокиП");
	ТаблицаСтрок = Новый ТаблицаЗначений;     
    ТаблицаСтрок.Колонки.Добавить("НомерСтрокиП");

/////////////////////////////////////////////////////////////////////////////////	
//Цикл от первого элемента к последнему
Для СтартСчетчик = 0 По КоличествоСтрокТаб-1 Цикл
  Счетчик = СтартСчетчик;//стартовое смещение
	ТаблицаСтрок.Очистить();
	ТекущаяСумма = 0;	
  Для ТекущийСчетчик = 0 По КоличествоСтрокТаб-1 Цикл //переменная нигде
    //не используется, это клон первого цикла , контроль количества повторений,
    //а первый цикл только задает последовательный обход с кого начинать
	
    Если Счетчик = КоличествоСтрокТаб Тогда  //если уходим за таблицу то в начало
Счетчик = 0;	
КонецЕсли;
    НоваяСтрока = ТаблицаСтрок.Добавить();//постепенно наполняем таблицу
НоваяСтрока.НомерСтрокиП = Счетчик;
ТекущаяСумма = ТекущаяСумма + Таблица000[Счетчик].ОбъемТары;
    //объем Количество "/" Количество помещающее на паллет

    ВнутреннийСчетчик = Счетчик+1;//временная переменная

    Если ВнутреннийСчетчик = КоличествоСтрокТаб Тогда 
      //если уходим за таблицу то в начало
ВнутреннийСчетчик = 0;	
КонецЕсли;

    Пока НЕ ВнутреннийСчетчик = СтартСчетчик Цикл 
      // с каждым углублением количество циклов сокращается
	
Если ТекущаяСумма > Эдиал + ОтклонениеВПлюс Тогда
        //если перебор
Прервать;
КонецЕсли; 

ВариантСуммы = ТекущаяСумма + Таблица000[ВнутреннийСчетчик].ОбъемТары;
Если  ВариантСуммы >= Эдиал - ОтклонениеВМинус И ВариантСуммы <= Эдиал + ОтклонениеВПлюс Тогда
        //если попадает сумма в наш период вычисляем разницу
РазницаСумм = ВариантСуммы - Эдиал;
        Если РазницаСумм < 0 тогда //убираем минусы
РазницаСумм = РазницаСумм * -1;
КонецЕсли;

Если РазницаСумм < ОптимальнаяРазница Тогда
ОптимальнаяРазница = РазницаСумм;
ОптимальнаяСумма = ВариантСуммы;
Для Каждого Стр Из ТаблицаСтрок Цикл
            //записываем цепочку индексов строк
НоваяСтрока = ОптимальнаяТаблицаСтрок.Добавить();
НоваяСтрока.НомерСтрокиП = Стр.НомерСтрокиП;
КонецЦикла;	
          //дополняем из временной переменной
НоваяСтрока = ОптимальнаяТаблицаСтрок.Добавить();
НоваяСтрока.НомерСтрокиП = ВнутреннийСчетчик;

	

Сообщить(Строка(ОптимальнаяСумма));
КонецЕсли;

КонецЕсли;
ВнутреннийСчетчик = ВнутреннийСчетчик +1;
      //если уходим за таблицу то в начало
Если ВнутреннийСчетчик = КоличествоСтрокТаб Тогда
ВнутреннийСчетчик = 0;	
КонецЕсли;
КонецЦикла;//Пока Цикл
Если ТекущаяСумма > Эдиал + ОтклонениеВПлюс Тогда
Прервать;
КонецЕсли;
Счетчик = Счетчик+1;
КонецЦикла;
/////////////////////////////////////////////////////////////////////////////////////
КонецЦикла;
//добавление колонок и очистка данных 
ОднаТаблица = Новый ТаблицаЗначений;
ОднаТаблица = Таблица000.Скопировать();
ОднаТаблица.Очистить();
Для Каждого Стро Из ОптимальнаяТаблицаСтрок Цикл
НоваяСтрока = ОднаТаблица.Добавить();
  //заполнение нужных строк
ЗаполнитьЗначенияСвойств(НоваяСтрока, Таблица000[Стро.НомерСтрокиП]);	
КонецЦикла;

Расскажу о своей задаче в общем:

В самой стартовой разработке у меня много данных хранилось в переменных, что порождало сбои в программе. Но в 1с есть очень хорошее решение связка Документ — «Регистр остатков» , остается создать документ «прихода», а потом раскидывая товар по паллетам создавая «расход» мы в любую секунду запросом получаем нераспределенный остаток товара, главное только каждый раз очищать документы перед следующим распределением. Будут конкретные вопросы в комментариях, буду рад помочь.

Товары поделены на однотипности, параметры «Фасовка» и «ВидФасовки» за их определение отвечают. В «приходе» не заполняется номер паллета, а вычисляется вышеуказанным методом.

//ОбработкаПроведения(Отказ, Режим)
//Создаем документ с табличной частью, и булево переменной "Приход"
//таким образом мы понимаем что приход, а что расход
Если Приход = Истина Тогда
	// регистр РегистрРаспределениеНаПаллеты Приход
	Движения.РегистрРаспределениеНаПаллеты.Записывать = Истина;
	Для Каждого ТекСтрокаПродукция Из Продукция Цикл
		Движение = Движения.РегистрРаспределениеНаПаллеты.Добавить();
		Движение.ВидДвижения = ВидДвиженияНакопления.Приход;
		Движение.Период = Дата;
		Движение.Приход = Приход;
		Движение.Вариант = Вариант;
		Движение.Номенклатура = ТекСтрокаПродукция.Номенклатура;
		Движение.Характеристика = ТекСтрокаПродукция.Характеристика;
		Движение.НомерПалета = ТекСтрокаПродукция.НомерПалета;
		Движение.Однотипность = ТекСтрокаПродукция.Однотипность;
		Движение.Фасовка = ТекСтрокаПродукция.Фасовка;
		Движение.ВидФасовки = ТекСтрокаПродукция.ВидФасовки;
		Движение.ОбъемТары = ТекСтрокаПродукция.ОбъемТары;
		Движение.КоличествоНаОдинПаллет = ТекСтрокаПродукция.КоличествоНаОдинПаллет;
		Движение.Количество = ТекСтрокаПродукция.Количество;
		Движение.Партия = ТекСтрокаПродукция.Партия;
		Движение.ЕдиницаИзмерения = ТекСтрокаПродукция.ЕдиницаИзмерения;
	КонецЦикла;
Иначе
	// регистр РегистрРаспределениеНаПаллеты Расход
	Движения.РегистрРаспределениеНаПаллеты.Записывать = Истина;
	Для Каждого ТекСтрокаПродукция Из Продукция Цикл
		Движение = Движения.РегистрРаспределениеНаПаллеты.Добавить();
		Движение.ВидДвижения = ВидДвиженияНакопления.Расход;
		Движение.Период = Дата;
		Движение.Приход = Приход;
		Движение.Вариант = Вариант;
		Движение.Номенклатура = ТекСтрокаПродукция.Номенклатура;
		Движение.Характеристика = ТекСтрокаПродукция.Характеристика;
		Движение.НомерПалета = ТекСтрокаПродукция.НомерПалета;
		Движение.Однотипность = ТекСтрокаПродукция.Однотипность;
		Движение.Фасовка = ТекСтрокаПродукция.Фасовка;
		Движение.ВидФасовки = ТекСтрокаПродукция.ВидФасовки;
		Движение.ОбъемТары = ТекСтрокаПродукция.ОбъемТары;
		Движение.КоличествоНаОдинПаллет = ТекСтрокаПродукция.КоличествоНаОдинПаллет;
		Движение.Количество = ТекСтрокаПродукция.Количество;
		Движение.Партия = ТекСтрокаПродукция.Партия;
		Движение.ЕдиницаИзмерения = ТекСтрокаПродукция.ЕдиницаИзмерения;
	КонецЦикла;
КонецЕсли;

Стартовый обход документа «Приход».

&НаСервере
Функция ФункцияОбходаПрихода() Экспорт
Запрос = Новый Запрос;
	Запрос.Текст =
	
	"ВЫБРАТЬ
	|	РегистрРаспределениеНаПаллеты.Период,
	|	РегистрРаспределениеНаПаллеты.Регистратор,
	|	РегистрРаспределениеНаПаллеты.НомерСтроки,
	|	РегистрРаспределениеНаПаллеты.Активность,
	|	РегистрРаспределениеНаПаллеты.ВидДвижения,
	|	РегистрРаспределениеНаПаллеты.Приход,
	|	РегистрРаспределениеНаПаллеты.Вариант,
	|	РегистрРаспределениеНаПаллеты.Номенклатура,
	|	РегистрРаспределениеНаПаллеты.Характеристика,
	|	РегистрРаспределениеНаПаллеты.НомерПалета,
	|	РегистрРаспределениеНаПаллеты.Однотипность,
	|	РегистрРаспределениеНаПаллеты.Фасовка,
	|	РегистрРаспределениеНаПаллеты.ВидФасовки,
	|	РегистрРаспределениеНаПаллеты.ОбъемТары,
	|	РегистрРаспределениеНаПаллеты.КоличествоНаОдинПаллет,
	|	РегистрРаспределениеНаПаллеты.Партия,
	|	РегистрРаспределениеНаПаллеты.МоментВремени,
	|	РегистрРаспределениеНаПаллеты.ЕдиницаИзмерения,
	|	РегистрРаспределениеНаПаллеты.Количество
	|ИЗ
	|	РегистрНакопления.РегистрРаспределениеНаПаллеты КАК РегистрРаспределениеНаПаллеты
	|ГДЕ
	|	РегистрРаспределениеНаПаллеты.ВидДвижения = ЗНАЧЕНИЕ(ВидДвиженияНакопления.Приход)";
	Выборка = Запрос.Выполнить().Выбрать();
	//Выборка.Следующий();
	Возврат Выборка;
КонецФункции

Функция вычисления следующего паллета для распределения.

&НаСервере
Функция ФункцияМаксимальныйНомерПаллетаПлюсОдин() Экспорт//Следующий
Запрос = Новый Запрос;
	Запрос.Текст =	
	"ВЫБРАТЬ
	|	МАКСИМУМ(РегистрРаспределениеНаПаллеты.НомерПалета) КАК НомерПалета
	|ИЗ
	|	РегистрНакопления.РегистрРаспределениеНаПаллеты КАК РегистрРаспределениеНаПаллеты";
	Выборка = Запрос.Выполнить().Выбрать();
	Выборка.Следующий();
	Если ЗначениеЗаполнено(Выборка.НомерПалета) Тогда
		Возврат Выборка.НомерПалета+1;
	Иначе
		Возврат 1;
	КонецЕсли;
КонецФункции

Далее два запроса на поиск остатков свободного товара, готового к распределению. Параметры «Начало» и «Конец» отвечают за выбираемый объем если требуется. Однотипность — число от 1 и выше.

&НаСервере
Функция ФункцияОстатковСвободныхПоОднотипности(Однотипность, Начало, Конец) Экспорт
Запрос = Новый Запрос;
Запрос.Текст =
	"ВЫБРАТЬ
	|	РегистрРаспределениеНаПаллетыОстатки.Номенклатура,
	|	РегистрРаспределениеНаПаллетыОстатки.Характеристика,
	|	РегистрРаспределениеНаПаллетыОстатки.Однотипность КАК Однотипность,
	|	РегистрРаспределениеНаПаллетыОстатки.Фасовка,
	|	РегистрРаспределениеНаПаллетыОстатки.ВидФасовки,
	|	РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет,
	|	РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток КАК Количество,
	|	РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет КАК ОбъемТары,
	|	РегистрРаспределениеНаПаллетыОстатки.ЕдиницаИзмерения,
	|	РегистрРаспределениеНаПаллетыОстатки.Партия
	|ИЗ
	|	РегистрНакопления.РегистрРаспределениеНаПаллеты.Остатки КАК РегистрРаспределениеНаПаллетыОстатки
	|ГДЕ
	|	РегистрРаспределениеНаПаллетыОстатки.Однотипность = &Однотипность
	|	И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет <= &Конец
	|	И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет > &Начало
	|
	|УПОРЯДОЧИТЬ ПО
	|	ОбъемТары УБЫВ";
	Запрос.УстановитьПараметр("Однотипность", Однотипность);
	Запрос.УстановитьПараметр("Начало", Начало);
	Запрос.УстановитьПараметр("Конец", Конец);
Результат = Запрос.Выполнить();
Возврат Результат;
КонецФункции

// по всем остаткам
&НаСервере 
Функция ФункцияОстатковСвободных(Начало, Конец) Экспорт
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
|	РегистрРаспределениеНаПаллетыОстатки.Номенклатура,
|	РегистрРаспределениеНаПаллетыОстатки.Характеристика,
|	РегистрРаспределениеНаПаллетыОстатки.Однотипность КАК Однотипность,
|	РегистрРаспределениеНаПаллетыОстатки.Фасовка,
|	РегистрРаспределениеНаПаллетыОстатки.ВидФасовки,
|	РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет,
|	РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток КАК Количество,
|	РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет КАК ОбъемТары,
|	РегистрРаспределениеНаПаллетыОстатки.ЕдиницаИзмерения,
|	РегистрРаспределениеНаПаллетыОстатки.Партия
|ИЗ
|	РегистрНакопления.РегистрРаспределениеНаПаллеты.Остатки КАК РегистрРаспределениеНаПаллетыОстатки
|ГДЕ
|	РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет <= &Конец
|	И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет > &Начало
|
|УПОРЯДОЧИТЬ ПО
|	ОбъемТары УБЫВ";
Запрос.УстановитьПараметр("Начало", Начало);
Запрос.УстановитьПараметр("Конец", Конец);
Результат = Запрос.Выполнить();
Возврат Результат;
КонецФункции

Функция записи документа.

НомерПалета = ФункцияМаксимальныйНомерПаллетаПлюсОдин();//вышеуказанная
ПеременнаяОбъема = 0;
//цикл по полученной таблице
Для каждого СтрокаТЗ Из ОднаТаблица Цикл
	ПеременнаяОбъема = ПеременнаяОбъема + СтрокаТЗ.ОбъемТары;
	Если ПеременнаяОбъема <= Число("1,05") Тогда 
    //////////////////////////// пока не перебор, записывать			 
НоваяСтрока = НовыйДокумент.Продукция.Добавить();
ЗаполнитьЗначенияСвойств(НоваяСтрока, СтрокаТЗ);
НоваяСтрока.НомерПалета = НомерПалета;
////////////////////////////
	Иначе
		Прервать;
	КонецЕсли;
КонецЦикла;
НовыйДокумент.Записать(РежимЗаписиДокумента.Проведение);

Самый простой способ решения выглядит так:

Проблема в том, что нам нужно найти решение как можно быстрее, а выписывать и потом складывать 120 чисел — долго. Дело в том, что общее количество перестановок без повторений из пяти элементов — это 5!, то есть факториал пяти:

5! = 1 × 2 × 3 × 4 × 5

Ещё можно ошибиться в одной из комбинаций и из-за этого получить неправильный ответ. Так что это точно не самый быстрый способ решения задачи.

Если у нас есть под рукой браузер и пять свободных минут, можно написать код, который простым перебором найдёт все комбинации и посчитает их сумму. Логика кода будет такая:

На всё это пяти минут хватит с запасом, если писать код без комментариев. Раз у нас под рукой только браузер, напишем код на JavaScript. Запускаем код и видим в консоли ответ:

3 999 960

Вручную такое мы бы точно считали очень долго.

👉 Спасательный круг для тех, кто начинает писать на JavaScript

// функция для получения всех перестановок
const permutator = (inputArr) => {
  // итоговый массив
  let result = [];
  // создаём вложенную функцию
  const permute = (arr, m = []) => {
    // если в массиве не осталось элементов
    if (arr.length === 0) {
      // добавляем новый элемент в промежуточный массив
      result.push(m)
    // в ином случае
    } else {
      // перебираем все элементы массива
      for (let i = 0; i < arr.length; i++) {
        // получаем начало очередной комбинации
        let curr = arr.slice();
        // сдвигаем на единицу и формируем окончание
        let next = curr.splice(i, 1);
        // рекурсивно обрабатываем вторую часть массива
        permute(curr.slice(), m.concat(next))
     }
   }
 }
 // переставляем элементы массива
 permute(inputArr)
 // возвращаем результат
 return result;
}

// сумма всех чисел-перестановок
var sum = 0;
// получаем все перестановки из пяти чисел
var a = permutator([1,2,3,4,5]);

// перебираем все 120 комбинаций
for (let i = 0; i < 120; i++){
  // в каждой перебираем все 5 внутренних цифр
  for (let j = 0; j < 5; j++){
    // добавляем к сумме текущее пятизначное число
    sum += a[i][j]*Math.pow(10,j);
  } 
}

// выводим результат
console.log(sum);

Это решение может оказаться быстрее предыдущего, потому что нам не нужно будет тестировать код и перепроверять логику его работы. Вместо кода мы сделаем такую хитрость: 

Применим ту же формулу нахождения количества перестановок, что и в первом решении — для 4 цифр количество вариантов равно 4! Если мы учтём, что пятёрка стоит на первом месте в числе, получится такое:

5(10⁴) × 4! — это общая сумма пятёрок во всех комбинациях, если она стоит на первом месте.

Точно так же посчитаем сумму всех пятёрок, если они будут стоять на втором месте, то есть на месте тысяч:

Количество перестановок останется таким же, только поменяется степень десятки — теперь цифра 5 отвечает за тысячи:

5(10³) × 4! — это общая сумма пятёрок во всех комбинациях, если она стоит на втором месте.

Таким же способом находим общие суммы пятёрок на остальных местах:

5(10²) × 4! — общая сумма пятёрок на третьем месте (сотни)

5(10¹) × 4! — на четвёртом месте (десятки)

5(10⁰) × 4! — на пятом месте (единицы)

Итого, если найти сумму всех пятёрок во всех комбинациях на разных местах, у нас выйдет такое:

5(10⁴) × 4 + 5(10³) × 4! + 5(10²) × 4! + 5(10¹) × 4! + 5(10⁰) × 4!

Вынесем общие множители за скобки:

5 × (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

Получается, единственное, что влияет на общую сумму в случае одного числа — это оно само в виде первого множителя. По аналогии найдём суммы остальных чисел на разных позициях:

4 × (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

3 × (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

2 × (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

1× (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

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

(5 + 4 + 3 + 2 + 1) × (10⁴ + 10³ + 10² +10¹ + 10⁰) × 4!

15 × (1000 + 1000 + 100 +10 + 1) × 4!

15 × 1111 × 4!

15 × 1111 × 24 ← такое можно легко посчитать на листочке или калькуляторе

Перемножив числа, получим тот же ответ, что и с кодом — 3 999 960

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

Запрос: Есть пять цифр: 1, 2, 3, 4, 5. С помощью перестановок из них составили все возможные комбинации пятизначных чисел. Найди сумму этих чисел. Прокомментируй решение.

Ответ модели ChatGPT 3.5: 

Чтобы найти сумму всех возможных комбинаций пятизначных чисел из пяти данных цифр, нужно сначала определить, сколько раз каждая цифра может стоять на каждой позиции в числе. Так как мы имеем дело с пятизначными числами, каждая цифра может стоять на каждой из пяти позиций, т. е. по пять раз. Таким образом, каждая цифра будет встречаться 5! = 120 раз во всех возможных комбинациях.

Для нахождения суммы всех чисел можно использовать следующий алгоритм:

Таким образом:

Сумма цифр, умноженных на 11111 = 1*11111 + 2*11111 + 3*11111 + 4*11111 + 5*11111 = 123455

Сумма всех возможных комбинаций = 123455 * 120 = 14,814,600

Ответ: 14,814,600.

Примечание редакции: пока что не смог.

There are a lot of solutions so far, but all are of the form generate then filter. Which means that they potentially spend a lot of time working on recursive paths that do not lead to a solution.

Here is a solution that is O(size_of_array * (number_of_sums + number_of_solutions)). In other words it uses dynamic programming to avoid enumerating possible solutions that will never match.

For giggles and grins I made this work with numbers that are both positive and negative, and made it an iterator. It will work for Python 2.3+.

def subset_sum_iter(array, target):
    sign = 1
    array = sorted(array)
    if target < 0:
        array = reversed(array)
        sign = -1
    # Checkpoint A

    last_index = {0: [-1]}
    for i in range(len(array)):
        for s in list(last_index.keys()):
            new_s = s + array[i]
            if 0 < (new_s - target) * sign:
                pass # Cannot lead to target
            elif new_s in last_index:
                last_index[new_s].append(i)
            else:
                last_index[new_s] = [i]
    # Checkpoint B

    # Now yield up the answers.
    def recur(new_target, max_i):
        for i in last_index[new_target]:
            if i == -1:
                yield [] # Empty sum.
            elif max_i <= i:
                break # Not our solution.
            else:
                for answer in recur(new_target - array[i], i):
                    answer.append(array[i])
                    yield answer

    for answer in recur(target, len(array)):
        yield answer

And here is an example of it being used with an array and target where the filtering approach used in other solutions would effectively never finish.

def is_prime(n):
    for i in range(2, n):
        if 0 == n % i:
            return False
        elif n < i * i:
            return True
    if n == 2:
        return True
    else:
        return False


def primes(limit):
    n = 2
    while True:
        if is_prime(n):
            yield(n)
        n = n + 1
        if limit < n:
            break


for answer in subset_sum_iter(primes(1000), 76000):
    print(answer)

This prints all 522 answers in under 2 seconds. The previous approaches would be lucky to find any answers in the current lifetime of the universe. (The full space has 2^168 = 3.74144419156711e+50 possible combinations to run through. That…takes a while.)

Explanation
I was asked to explain the code, but explaining data structures is usually more revealing. So I’ll explain the data structures.

Let’s consider subset_sum_iter([-2, 2, -3, 3, -5, 5, -7, 7, -11, 11], 10).

At checkpoint A, we have realized that our target is positive so sign = 1. And we’ve sorted our input so that array = [-11, -7, -5, -3, -2, 2, 3, 5, 7, 11]. Since we wind up accessing it by index a lot, here the the map from indexes to values:

0: -11
1:  -7
2:  -5
3:  -3
4:  -2
5:   2
6:   3
7:   5
8:   7
9:  11

By checkpoint B we have used Dynamic Programming to generate our last_index data structure. What does it contain?

last_index = {    
    -28: [4],
    -26: [3, 5],
    -25: [4, 6],
    -24: [5],
    -23: [2, 4, 5, 6, 7],
    -22: [6],
    -21: [3, 4, 5, 6, 7, 8],
    -20: [4, 6, 7],
    -19: [3, 5, 7, 8],
    -18: [1, 4, 5, 6, 7, 8],
    -17: [4, 5, 6, 7, 8, 9],
    -16: [2, 4, 5, 6, 7, 8],
    -15: [3, 5, 6, 7, 8, 9],
    -14: [3, 4, 5, 6, 7, 8, 9],
    -13: [4, 5, 6, 7, 8, 9],
    -12: [2, 4, 5, 6, 7, 8, 9],
    -11: [0, 5, 6, 7, 8, 9],
    -10: [3, 4, 5, 6, 7, 8, 9],
    -9: [4, 5, 6, 7, 8, 9],
    -8: [3, 5, 6, 7, 8, 9],
    -7: [1, 4, 5, 6, 7, 8, 9],
    -6: [5, 6, 7, 8, 9],
    -5: [2, 4, 5, 6, 7, 8, 9],
    -4: [6, 7, 8, 9],
    -3: [3, 5, 6, 7, 8, 9],
    -2: [4, 6, 7, 8, 9],
    -1: [5, 7, 8, 9],
    0: [-1, 5, 6, 7, 8, 9],
    1: [6, 7, 8, 9],
    2: [5, 6, 7, 8, 9],
    3: [6, 7, 8, 9],
    4: [7, 8, 9],
    5: [6, 7, 8, 9],
    6: [7, 8, 9],
    7: [7, 8, 9],
    8: [7, 8, 9],
    9: [8, 9],
    10: [7, 8, 9]
}

(Side note, it is not symmetric because the condition if 0 < (new_s - target) * sign stops us from recording anything past target, which in our case was 10.)

What does this mean? Well, take the entry, 10: [7, 8, 9]. It means that we can wind up at a final sum of 10 with the last number chosen being at indexes 7, 8, or 9. Namely the last number chosen could be 5, 7, or 11.

Let’s take a closer look at what happens if we choose index 7. That means we end on a 5. So therefore before we came to index 7, we had to get to 10-5 = 5. And the entry for 5 reads, 5: [6, 7, 8, 9]. So we could have picked index 6, which is 3. While we get to 5 at indexes 7, 8, and 9, we didn’t get there before index 7. So our second to last choice has to be the 3 at index 6.

And now we have to get to 5-3 = 2 before index 6. The entry 2 reads: 2: [5, 6, 7, 8, 9]. Again, we only care about the answer at index 5 because the others happened too late. So the third to last choice is has to be the 2 at index 5.

And finally we have to get to 2-2 = 0 before index 5. The entry 0 reads: 0: [-1, 5, 6, 7, 8, 9]. Again we only care about the -1. But -1 isn’t an index — in fact I’m using it to signal we’re done choosing.

So we just found the solution 2+3+5 = 10. Which is the very first solution we print out.

And now we get to the recur subfunction. Because it is defined inside of our main function, it can see last_index.

The first thing to note is that it calls yield, not return. This makes it into a generator. When you call it you return a special kind of iterator. When you loop over that iterator, you’ll get a list of all of the things it can yield. But you get them as it generates them. If it is a long list, you don’t put it in memory. (Kind of important because we could get a long list.)

What recur(new_target, max_i) will yield are all of the ways that you could have summed up to new_target using only elements of array with maximum index max_i. That is it answers: «We have to get to new_target before index max_i+1.» It is, of course, recursive.

Therefore recur(target, len(array)) is all solutions that reach target using any index at all. Which is what we want.

Если правильно понял ТС, то количество сумм по n-2 элементов будет равно количеству сумм по 2 элемента. (Например, если количество элементов равно 10, то количество сумм по 8 элементов равно количеству сумм по 2 элемента. Значения сумм можно вычислить через сумму всего массива. S{1,2,3,4,5,6,7,8}=S{всего массива}-S{9,10}). Соответственно количество сумм по n-3 элементов будет равно количеству сумм по 3 элемента. (Например, если количество элементов равно 10, то количество сумм по 7 элементов равно количеству сумм по 3 элемента. Значения сумм можно вычислить через сумму всего массива. S{4,5,6,7,8,9,10}=S{всего массива}-S{1,2,3}). Т.е до половины количества элементов сумма вычисляется, после половины вычитается из общей суммы.
Пример для n=10:

1
2
3
4
5
6
7
8
9

sum:=0;
for i:=1 to 10 do
 sum:=sum+a[i];
for i:=1 to 9 do
 for j:=2 to 10 do
  begin
   sum2:=a[i]+a[j];
   sum8:=sum-sum2
  end;