Based on your solution: def subsetsum(array,num): if num == 0 or num < 1: return None elif len(array) == 0: return None else: if array[0] == num: return [array[0]] else: with_v = subsetsum(array[1:],(num – array[0])) if with_v: return [array[0]] + with_v else: return subsetsum(array[1:],num)
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
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
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
Subset Sum is the first NP-complete problem I learned at Macalester. This question is viewed 36000+ times yet I don’t see a sufficient answer that explains the algorithm in detail with logic. So I thought I make an attempt to do so. Assumption: For the sake of simplicity first I made the assumption that the … Read more
Finding all possible combinations of numbers to reach a given sum