Bounded Solution Count Inclusion Exclusion

Problem

Count the nonnegative integer solutions to x1 + ... + xk = n with 0 <= xi <= c_i using inclusion-exclusion over subsets S: sum (−1)^|S| C(n - sum_{S}(c_i + 1) + k - 1, k - 1).

Given n, the number of variables k, and the bound list, return the count. Terms with a negative argument contribute zero.

Hint

Over-subtract for one violated bound, then add back pairs.

Test cases

case 1

in: [5,3,[3,3,3]]

expected: 12

case 2

in: [2,2,[1,1]]

expected: 1

case 3

in: [0,2,[1,1]]

expected: 1

Starter codePython

def bounded_solution_count_inclusion_exclusion(n, k, bounds):
    # Your code here
    pass

3 test cases · run your code against them in the editor