We have a requirement where we want to generate incremental numbers until a target number using a given set of numbers. (The given set of numbers may vary, and the algorithm needs to work for any set of numbers. Though, practically we are expecting the set to contain up to 15 numbers.)
Assumptions: All the numbers in the given set are assumed to be integers.
By incremental numbers I mean all the numbers possible by adding multiples of a given set of numbers.
E.g. Let's say the we have a set {12, 13, 17} and the target number is 50. Then the incremental numbers are {0, 12, 13, 17, 24, 25, 26, 29, 30, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 50}
(Explanation for the above incremental numbers:
0 = (12 * 0) + (13 * 0) + (17 * 0)
12 = (12 * 1) + (13 * 0) + (17 * 0)
13 = (12 * 0) + (13 * 1) + (17 * 0)
17 = (12 * 0) + (13 * 0) + (17 * 1)
24 = (12 * 2) + (13 * 0) + (17 * 0)
25 = (12 * 1) + (13 * 1) + (17 * 0)
26 = (12 * 0) + (13 * 2) + (17 * 0)
29 = (12 * 1) + (13 * 0) + (17 * 1)
30 = (12 * 0) + (13 * 1) + (17 * 1)
34 = (12 * 0) + (13 * 0) + (17 * 2)
36 = (12 * 3) + (13 * 0) + (17 * 0)
37 = (12 * 2) + (13 * 1) + (17 * 0)
38 = (12 * 1) + (13 * 2) + (17 * 0)
39 = (12 * 0) + (13 * 3) + (17 * 0)
41 = (12 * 2) + (13 * 0) + (17 * 1)
42 = (12 * 1) + (13 * 1) + (17 * 1)
43 = (12 * 0) + (13 * 2) + (17 * 1)
46 = (12 * 1) + (13 * 0) + (17 * 2)
47 = (12 * 0) + (13 * 1) + (17 * 2)
48 = (12 * 4) + (13 * 0) + (17 * 0)
49 = (12 * 3) + (13 * 1) + (17 * 0)
50 = (12 * 2) + (13 * 2) + (17 * 0)
)
Could anybody help me with an optimized solution for this ?
It's hard to do much better than a brute-force approach here. You can discard any number that is divisible by another number in the list. Then, you can use the following algorithm:
lst = [12,13,17]
target = 50
sums = {0}
for i in lst:
new_sums = set()
for j in sums:
x = j + i
while x <= target and x not in new_sums:
new_sums.add(x)
x += i
sums = sums.union(new_sums)
print(sums)
# {0, 12, 13, 17, 24, 25, 26, 29, 30, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 50}