[Python] Strategies for Enhancing Algorithm Efficiency?

I have this task:

Mother Anna opened a package of candies, which she wants to distribute to her children as a reward. So that they are not clashes between them, so of course the one who finished in a better place in the competition cannot get less candies than the one that ended up in a worse place. How many ways can Anna divide C candies among D children?

The task:
For the given numbers D and C, find the number of possible distributions of candies.

Entrance:
In the first line of the file there is a number Q indicating the number of sets. There are Q rows with a pair of numbers D and C.

• 1 ≤ Q ≤ 1000
• 1 ≤ D ≤ 100
• 1 ≤ C ≤ 5,000

Output:
The output of the program is the result for each set modulo (2^30)-1 on a separate line.

Example Input:

3
1 10
2 4
3 8


Output:

1
3
10


I made this code and it works, but when i have 1000 inputs i get **Timelimit ** in evaluator, can you help me make code that will work faster?

def generate_combinations(d, c, current_combination=None, combinations=None):
if current_combination is None:
current_combination = []

if combinations is None:
combinations = []

if d == 0:
if c == 0:
if all(current_combination <= current_combination[i + 1] for i in range(len(current_combination) - 1)):

combinations.append(list(current_combination))
return

for i in range(c + 1):
generate_combinations(d - 1, c - i, current_combination + , combinations)

return combinations

c = 8
d = 3

pocet = int(input())
for i in range(pocet):
d, c = map(int, input().split())
print(len(generate_combinations(d, c)))


I also have version using dynamic programming

def dynamic_programming(d, c):
dp = [[0] * (c + 1) for _ in range(d + 1)]
dp[0][0] = 1

for i in range(1, d + 1):
for j in range(c + 1):
dp[j] = dp[i - 1][j]
if j >= i:
dp[j] += dp[j - i]
dp[j] %= (2 ** 30 - 1)
b = dp[d][c]
return dp[d][c]

q = int(input().strip())

for i in range(q):
d, c = map(int, input().split())
print(dynamic_programming(d, c))


For better understending here is the example if we want to divide 8 candies among 3 children we have 21 possibilities:

[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[0, 5, 3]
[0, 6, 2]
[0, 7, 1]
[0, 8, 0]
[1, 0, 7]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[1, 4, 3]
[1, 5, 2]
[1, 6, 1]
[1, 7, 0]
[2, 0, 6]
[2, 1, 5]
[2, 2, 4]
[2, 3, 3]
[2, 4, 2]
[2, 5, 1]
[2, 6, 0]
[3, 0, 5]
[3, 1, 4]
[3, 2, 3]
[3, 3, 2]
[3, 4, 1]
[3, 5, 0]
[4, 0, 4]
[4, 1, 3]
[4, 2, 2]
[4, 3, 1]
[4, 4, 0]
[5, 0, 3]
[5, 1, 2]
[5, 2, 1]
[5, 3, 0]
[6, 0, 2]
[6, 1, 1]
[6, 2, 0]
[7, 0, 1]
[7, 1, 0]
[8, 0, 0]


And there is only 10 possibilities that fit for this task:

[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[2, 2, 4]
[2, 3, 3]

Continue reading...