Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

with N as the length of the subsets and X as the length of input, `combinations n xs` basically walks through list xs and at each element, conses that element onto each combination of size n-1 of later elements in the list then appends those resulting lists together. this is on the order of N * nCr(X, N) aka O(NX!/(N!(X-N)!)) which dominates the overall runtime. the final filter walks through each combination and does O(N) work at each element to find the ones that sum to the desired amount, again O(NX!/(N!(X-N)!))


Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: