wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

all_subset_sums_fft (374B)

      1 # All subset sums with FFT
      2 
      3 [Algorithm] for [all_subset_sums] using [FFT], running in Otilde(sum of the elements).
      4 
      5 Useful if the input is coded in [unary] for instance
      6 
      7 Source: [koiharis2019faster], Theorem 3.1
      8 
      9 Algorithm:
     10 - split elements into two halves
     11 - compute recursively all the sums of the halves
     12 - merge the sums using [FFT]
     13 
     14 Up: [algorithm] for [all_subset_sums]