subset-sum

Fast solution to Subset sum

by

I respect the alacrity with which you’re trying to solve this problem! Unfortunately, you’re trying to solve a problem that’s NP-complete, meaning that any further improvement that breaks the polynomial time barrier will prove that P = NP. The implementation you pulled from Hacker News appears to be consistent with the pseudo-polytime dynamic programming solution, … Read more

Subset sum Problem

by

I’m not quite sure if your solution is exact or a PTA (poly-time approximation). But, as someone pointed out, this problem is indeed NP-Complete. Meaning, every known (exact) algorithm has an exponential time behavior on the size of the input. Meaning, if you can process 1 operation in .01 nanosecond then, for a list of … Read more

Find all combinations of a list of numbers with a given sum

by

You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn’t sum to 10: import itertools numbers = [1, 2, 3, 7, 7, 9, 10] target = 10 result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == target] print(result) … Read more