Sprawdzanie czy z wartosci w liscie mozna wyliczyc konkretna liczbe

Question

Tak jak w temacie.

Jak sprawdzić czy z wartości w liście można utworzyć dana liczbę,korzystajac tylko z tych konkretnych wartosci.

Załóżmy:

list=[1,1,3,3,3,3,5,10,23,53]

Chcemy otrzymać liczbę np. 9, jak widać można utworzyć ja z liczb 1,3,5 wiec te elementy usuwam z listy i zostaje nam

list=[1,3,3,3,10,23,53]

Answer 1

Zadanie oparte jest o sprawdzanie struktury stosu.

1. Deklarujesz pustą listę rezultatów liczb do usunięcia (dla Twojego przykładu w wyniku później będzie 1,3,5)

2. Przeglądasz po kolei wartości z pierwotnej listy

3. Od wartości podanej (u Ciebie 9), odejmujesz daną wartość z pierwotnej listy oraz sumę poprzednich rezultatów.

4. Jeśli wynik jest równy zero, kończysz przeglądanie. Jeśli większy, odkładasz znalezioną wartość do rezultatów przeglądasz dalej. Jeśli mniejszy, zdejmujesz wartość z rezultatów i przeglądasz dalej.

5. Jeśli indeks dojdzie do końca i nie znalazł, zerujesz rezultaty.

Usunięcie elementów z listy rezultaty w pierwotnej liście jest już trywialne :-)