Как найти все возможные комбинации чисел от 1 до n-1 чтобы их сумма была равна n?

Question

[Евгений]

Доброй ночи) никак не могу придумать как решить задачку... есть число, например 8, нужно найти все числа от 1 до 7, сумма которых равна 8 без повторения... т.е. вариантов масса...
1, 7
2, 6
3, 5
1, 2, 5
1, 3, 4
Но не известно какое число... может быть 5, а может 534...
Пробовал создать массив чисел и пытаться рекурсивно выуживать все варианты, но получается не очень....
Подскажите, кто решал такое, алгоритм решения задачи, либо ссылочку ткните))) в гугле как не пробовал задать вопрос выдает обычно поиск в массиве пары чисел сумма которых равна n, но у меня нет ограничения сколько чисел должно быть... может 2, а может 8 а может еще сколько то... надо как-то идти по массиву и накидывать пока не получится нужная сумма или перебор, потом откатываться и пытаться дальше, и тут я запутываюсь, может совсем не в ту сторону рою...

Comments

[CyrilStr]

ааааа
можно на си щарп и до n, а не n-1
пожалуйста

Answer 1

[Wataru]

Вариант 1 - полный рекурсивный перебор. Есть одна рекурсивная функция, которой передается следующее число, текущая сумма и текущий список взятых чисел. Функция или берет следующее число или пропускает его и вызывается рекурсивно для следующего числа. Если сумма слишком большая - просто возвращается сразу. Если сумма равна n - выводит текущие числа и возвращается.

Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

Что-то типа такого:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

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

Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).

Comments

[Евгений]

Спасибо, буду думать)

[Евгений]

У меня все упирается в то, что как запоминать куда откатываться)) а то получится собирать одно и тоже))

[Wataru]

Евгений, Вам надо понять как работает рекурсия и стек вызовов. Вам не надо ничего запоминатать, оно само откатится куда надо. Код, что я привел - почти рабочее решение на C++, надо только if() в начале функции поменять местами.

Вот пример для n=2. Тут по вертикали время, а количество отступов соответствует глубине рекурсии.

Generate(1,0, {0}). 
  Вызывает Generate (2, 2, 0, {})
    Вызывает Generate(2, 3, 0, {})
    Вызывает Generate(2, 3, 2, {2})
  Вызывает Generate(2, 2, 1, {1})
    Вызывает Generate(2, 3, 1, {1})
    Вызывает Generate(2, 3, 3, {1,2})

Сначала функция с парматрами (2, 1, 0, {}) вызовет (2,2,0, {}). Эта функция что-то там рекурсивно повызывает, подсчитает и вернется. Потом будет вызов функции с параметрами (2,2,1,{}) двумя строчками ниже в коде. Обратите внимание, эти 2 вызова с одинаковым количеством отступов. Все, что правее их - вызвано ими рекурсивно. При этом на каждом уровне все локальные переменные и параметры хранятся в стеке. Поэтому когда фукция (2,2,0, {}) закончится, исполнение в функции будет иметь пустой массив taken, несмотря на то, что несколько циклов процессора назад переменная taken содержала число 2. Но это была другая копия taken, ниже по стеку, в другом вызове! В общем, я не могу вам нагляднее объяснить как работает рекурсия и функции. Гуглите, читайте книжки.

Ну или альтернатива, если так понятнее - перебирайте все подмножества как битовые числа без рекурсии (если чисел всего не более 64). Типа вот есть 3 числа {1,2,3} - назначьте каждому числу разряд. 1 - еденицы, 2 - двоичные десятки, 3 - сотни. Тогда любое подмножество соответсвует строке из 0 и 1 или битовому числу. Где стоят еденицы в двоичной записи числа - те числа и есть в множестве.

Вроде как {} = 0, {1} = 001(2) = 1, {2} = 010(2) = 2, {1,2} = 011(2) = 3, {3} = 4, {1,2,3} = 7.
При этом строка 11010 или число 26 будет соответствовать множеству {2,4,5}.

Теперь можно все подмножества перебирать просто циклом от 0 до 2^n - 1. Потом битовыми операциями извлечь биты из переменной-индекса, преобразовать их в список чисел, просуммировать и сравнить с n.
Тут нужно будет или с битовыми сдвигами и пробитовыми и работать или с операциями взятия остатка от деления на 2. Если чисел больше 64 - то надо реализовывать битовую арифметику на строке из 0 и 1 и столбиком прибавлять в нее 1.

Но это решение не оптимизировать, оно будет всегда перебирать все подмножества, даже заведомо бесполезные. Типа если вам надо собрать 100, то вы будете перебирать 2^97 подмножеств с {99, 98}, хотя там сумма точно будет больше 100. В рекурсивной реализации, которая собирает множества постепенно можно впихнуть всякие оптимизации, типа раннего выхода, если сумма уже слишком большая.

Answer 2

[TaganTrader]

Если все же на JS то вот так

function variants(a, r) {
  return [...Array(2**a.length)].map((x,i)=>a.filter((x,j)=>i&1<<j).sort()).filter((x,i)=>eval(x.join`+`)==r);
}

// Пример использования
console.log(variants([7, 8, 3, 4, 5, 6, 1, 2], 8)) // [[8],[3,5],[1,7],[1,3,4],[2,6],[1,2,5]]

Answer 3

[xmoonlight]

Обход бинарного "дерева".

Comments

[Евгений]

Чет не могу представить структуру...

[xmoonlight]

Евгений, нужное число делим пополам и округляем вверх - это root.
Потом - слева направо заполняем по 2 ветки составными числами родительского узла.
Затем - обходим дерево и готово.

[Евгений]

xmoonlight, чет времени пока нет) попробую на днях, разгребу все что посоветовали и рабочие варианты поотмечаю решениями)

Answer 4

[uvelichitel]

Если алгоритм поиска пар у вас есть, просто применяйте его рекурсивно к элементам пар.

Comments

[jcmvbkbc]

без повторения

применяйте его рекурсивно к элементам пар

К одному -- меньшему элементу.

[Евгений]

jcmvbkbc, ну повторение потом можно отфильтровать.... только видимо мозги поплыли уже совсем))) беру элемент пары и ищу что?))

Answer 5

[Somewhere Intech]

на маленьких работает, на больших проверить возможности нет

function* genz( n ){
	for ( let i = n-1; i > 1; i--){
		let a = n - i;
		if (a < i) yield [i,a]
		for (let d of [...genz(a)])
			if (!d.some(value => value >= a || value >= i)) yield [i, ...d]
	}
}

//pretty print
console.log([...genz(13)].map(v=>v.join(' + ')).join('\r\n'), '\r\n');

Comments

[Евгений]

Спасибо, чуть позже проверю)

Answer 6

[Zanak]

Такой вариант вроде работает:

package main

import "fmt"

func sum(s []int) int {
	result := 0
	for _, v := range s {
		result = result + v
	}
	return result
}

func main() {
	n := 10000
	var stack []int
	p := n - 1
	for p > 0 {
		stack = append(stack, p)
		for j := p - 1; j > 0; j-- {
			stack = append(stack, j)
			cur := sum(stack)
			if cur < n {
				continue
			} else if cur == n {
				fmt.Printf("%++v\n", stack)
			}
			stack = stack[:len(stack)-1]
		}
		stack = nil
		p--
	}
}

Прошу прощения, на node не пишу.

Comments

[Евгений]

Катастрофически не хватает времени все проверить) чуть позже дрберусь) спасибо