Kasperenysh
@Kasperenysh
Рецидив в особо острой форме))

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

Доброй ночи) никак не могу придумать как решить задачку... есть число, например 8, нужно найти все числа от 1 до 7, сумма которых равна 8 без повторения... т.е. вариантов масса...
1, 7
2, 6
3, 5
1, 2, 5
1, 3, 4
Но не известно какое число... может быть 5, а может 534...
Пробовал создать массив чисел и пытаться рекурсивно выуживать все варианты, но получается не очень....
Подскажите, кто решал такое, алгоритм решения задачи, либо ссылочку ткните))) в гугле как не пробовал задать вопрос выдает обычно поиск в массиве пары чисел сумма которых равна n, но у меня нет ограничения сколько чисел должно быть... может 2, а может 8 а может еще сколько то... надо как-то идти по массиву и накидывать пока не получится нужная сумма или перебор, потом откатываться и пытаться дальше, и тут я запутываюсь, может совсем не в ту сторону рою...
  • Вопрос задан
  • 236 просмотров
Решения вопроса 1
wataru
@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).
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Обход бинарного "дерева".
Ответ написан
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Если алгоритм поиска пар у вас есть, просто применяйте его рекурсивно к элементам пар.
Ответ написан
john36allTa
@john36allTa
That`s calling Walker
на маленьких работает, на больших проверить возможности нет
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');
Ответ написан
@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 не пишу.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы