There is a number C given (C is an integer) and there is given a list of numbers (let's call it N, all the numbers in list N are integers). My task is to find the amount of possibilities to represent C.
For example:
input:
C = 4
N = [1, 2]
output:
3
Because:
4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2
My code is working pretty well for small numbers. However I have no idea how can I optimize it so it will work for bigger integers too. Any help will be appreciated!
There is my code:
import numpy
import itertools
def amount(C):
N = numpy.array(input().strip().split(" "),int)
N = list(N)
N = sorted(N)
while C < max(N):
N.remove(max(N))
res = []
for i in range(1, C):
for j in list(itertools.combinations_with_replacement(N, i)):
res.append(sum(list(j)))
m = 0
for z in range (0, len(res)):
if res[z] == C:
m += 1
if N[0] == 1:
return m + 1
else:
return m
Complexity of your algorithm is
O(len(a)^С)
. To solve this task more efficiently, use dynamic programming ideas.Assume
dp[i][j]
equals to number of partitions ofi
using termsa[0], a[1], ..., a[j]
. Arraya
shouldn't contain duplicates. This solution runs inO(C * len(a)^2)
time.