Problem ogólny nazywa się SubsetSum i jest NP-zupełny ;) https://en.wikipedia.org/wiki/Subset_sum_problem Ale że masz potęgi 2 i nic się nie powtarza, to można faktycznie trywialnie rozłożyć wejściową liczbę na bity. Nie wiem tylko gdzie jest problem z rozmiarem liczb skoro mozesz zrobić tu zwykłą tablicę bitów i tyle. Nie trzeba żadnego bignuma tutaj robić. Robimy np. tak:
S1 = [1, 2, 8, 16, 64, 128]
set_bits = {int(math.log(x, 2)) for x in S1}
i cyk, mamy informacje które bity są dla nas "dostepne". Teraz wystarczy rozłożyć N na bity i sprawdzać czy jeśli i-ty bit N jest 1
to czy mamy i
w zbiorze set_bits
.
Przykład:
import math
def main():
N = 6
S1 = [1, 2, 8, 16, 64, 128]
set_bits = {int(math.log(x, 2)) for x in S1}
bits = []
while N != 0:
bits.append(N % 2)
N /= 2
result = []
for index, bit in enumerate(bits):
if index not in set_bits:
print("Nie da sie, brakuje nam %d" % 2 ** index)
result = None
else:
result.append(2 ** index)
if result:
print("Rozwiazanie: %s" % result)
main()
Żadnych bignumów ani innych cudów :)