Sunday, September 19, 2021

Dynamic Programming - FFT Subset Sum problem

import numpy as np

import math

s = [1,2,3,5,10, 15, 20]

#print("Set", s)

n= int(math.pow(2,len(s)))

#print(power, n)

A = np.zeros(n)

C1 = []

for item in s:

    A[item] = 1

A1 = np.fft.fft(A)

# print(len(A1), type(A1), A1)

for i in range(0,n,1):

    C1.append(A1[i]*A1[i]*A1[i])

C = np.fft.ifft(C1)

#print(C, C[19].real)

for i in range(0,n,1):

    if C[i].real>=.999999:

        print(i,"yes")

    else:

        print(i,"no")