Algorytm wyszukiwania wszystkich kombinacji sum

[hajzus]

Witam,

 

Chcem napisac program, ktory bedzie mi wypisywal na ekran lub zapisywal do pliku (to juz sobie sam zrobie ) wszystkie mozliwe sumy utrzymane z danych liczb. Przyklad:

 

Mam zadeklarowana tablice 4ro elementowa o elementach 1,2,3,4. Chce aby program znajdowal wszystkie mozliwe sumy uzyskane z tych 4 liczb, czyli w tym przypadku beda to:

 

1 = 1

2 = 2

3 = 3

4 = 4

1+2 = 3

1+3 = 4

1+4 = 5

2+3 = 5

2+4 = 6

3+4 = 7

1+2+3 = 6

1+2+4 = 7

1+3+4 = 8

2+3+4 = 9

1+2+3+4 = 10

 

Oczywiscie jest to tylko przyklad pogladowy, ale do wyznaczenia algorytmu jest latwy Jesli, ktores z sum dadza taki sam wynik, to i tak zapisze mi je jako oddzielna wartosc. Oczywiscie pomijamy przypadki 1+2 i 2+1, bo dodawanie jest naprzemienne.

 

Chodzi mi o algorytm, pomysl, a nie gotowy kod programu

 

 

Serdecznie pozdrawiam i z gory dziekuje za pomoc

[Toster]

robisz dodawanie na systemie n-liczbowym w twoim przypadku 4 kowym

zpisujesz w nim liczbe 1111

przy czym kazda pozycja to index do tablicy w ktorej masz swoje liczby, robisz sume elementow tablicy wskazanych indexami, zwiekszasz liczbe 1111 o 1 zgodnie z systemem czworkowym. Dodajesz alg. sprawdzania przemiennosci (albo odrzucasz sumy ktore juz wystapily) i powinno byc ok.

Przynajmniej taki mam pierwszy pomysl

[hajzus]

robisz dodawanie na systemie n-liczbowym w twoim przypadku 4 kowym

zpisujesz w nim liczbe 1111

przy czym kazda pozycja to index do tablicy w ktorej masz swoje liczby, robisz sume elementow tablicy wskazanych indexami, zwiekszasz liczbe 1111 o 1 zgodnie z systemem czworkowym. Dodajesz alg. sprawdzania przemiennosci (albo odrzucasz sumy ktore juz wystapily) i powinno byc ok.

Przynajmniej taki mam pierwszy pomysl

 

 

A co w momencie jak taka tablica bedzie miala powiedzmy 50 lub 100 liczb ??

[Toster]

system liczenia moze miec dowolny wymiar. To ze my uzywamy 10 kowego albo 2, 8, 16 nie znaczy ze system nie moze miec jako bazy liczby 181832291

[Force]

Posortować liczby i iść pętlę i od 0 do n-1, a i drugą (po j) od i do n-1 i sumować liczby z przedziału i do j