CODEWITHSUNDEEP
mathcombinationsbacktrackingrecursive-backtracking
Obito Kang
Obito Kang

Reputation: 1

How many sum of repeatable combinations of length N?

How many sum of repeatable combinations of length N ?

Like [1,3,5,10], N = 4.

And there gonna be

[1,1,1,1] -> sum is 4

[1,1,1,3] -> sum is 6

...

[10,10,10,10] -> sum is 40

I perform a backtracking algo. by python3

res = set()
n = 4
def backtrack(k, path):
    if len(path) == n:
        res.add(sum(path))
        return
    backtrack(k+1, path+[1])
    backtrack(k+1, path+[3])
    backtrack(k+1, path+[5])
    backtrack(k+1, path+[10])
    return
backtrack(0, list())

Is there has more efficient solution?

Upvotes: 0

Views: 51

Answers (2)

MBo
MBo

Reputation: 80187

O(n*len(list)*numberofdistinctsums) approach.

We have two sets containing current possible sums for odd and even steps. We calculate new sums formed with i+1 summands from previous step sums (with i summands).

For example, after two rounds we have all possible sums of two summands. Getting sum 8 from previous set, we put sums of three summands 8+1, 8+3,8+5, 8+10 into new set and so on.

a = [1,3,5,10]
n = 4
sums = [set(a), set()]
for i in range(1, n):
    sums[i%2].clear
    for j in sums[(i+1)%2]:
        for x in a:
            sums[i%2].add(j + x)

print(len(sums[(n-1)%2]))

Upvotes: 0

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

If n elements order be not important, then your code is wrong for example [1,1,2,2] ~ [1,2,1,2]

You can create a new list and repeat each element of the original n times. then the question is how many ways we can select n item from new list which can be calculated easily further more if you want the result set of all the sums i think there's no better way than iterating in all situations.

Upvotes: 1

Related Questions