Finding all combinations that sum up to a specific number with given constrains

Question

This is a continuation of this problem. Find all combinations that sum up to a specific number

Think of following values.

T = Target // The value to target. eg 100
I = Items // Number of items that makes T. eg 5

Now Not just like previous question, I want the numbers to be increased by an interval step (instead of $1$) like $2$, $5$, $10$, etc. The step value is $S$ (eg: $2$, $5$, $10$).

Also $H_i$ will tell what is the maximum value specific I will reach and $L_i$ will tell what is the lowest value specific I will start with.

Eg:

$T = 100$, $I = 3$, $S = 2$
$L_1 = 10$, $L_2 = 20$, $L_3 = 0$
$H_1 = 100$, $H_2 = 80$, $H_3 = 80$

If above are the value, all combination will look like below

010, 020, 070
010, 022, 068   ;Always Increasing / Decrease by 2 since S = 2
010, 024, 066
010, 026, 064
.....           ;After many  combinations
010, 080, 000
012, 020, 068
012, 022, 066
.....
.....
080, 018, 002
080, 020, 000   

Even though $H_1=100$, $I_1$ cannot reach $100$ since $L_2=20$.

What is the formula to find number if combination we can arrive with if $T$, $I$, $S$, $H_i$ and $L_i$ are given? Even solution as programming is enough.

Answer 1

Based on additional information given in the comments above, the problem can be stated as:

Given nonnegative integers $T, I, S$ such that $S \mid T$. Find the number of integer solutions to$$ \sum_{k = 1}^I x_k = T $$ with constraints$$ L_k \leqslant x_k \leqslant H_k,\ S \mid x_k, \quad k = 1, \cdots, I $$ where $L_k$'s and $H_k$'s are given nonnegative integers such that $S \mid L_k$, $S \mid H_k$, and $L_k \leqslant H_k$.

Define $T' = \dfrac{1}{S} \left( T - \sum\limits_{k = 1}^I L_k \right)$, $M_k = \dfrac{1}{S} (H_k - L_k)$, $y_k = \dfrac{1}{S} (x_k - L_k)$, then the problem is equivalent to find the number of integer solutions to$$ \sum_{k = 1}^I y_k = T' $$ with constraints$$ 0 \leqslant y_k \leqslant M_k. \quad k = 1, \cdots, I $$

Now define $f(0, 0) = 1$, $f(0, m) = 0\ (m ≠ 0)$, and $f(n, m)\ (1 \leqslant n \leqslant I)$ as the number of integer solutions to$$ \sum_{k = 1}^n y_k = m $$ with constraints$$ 0 \leqslant y_k \leqslant M_k. \quad k = 1, \cdots, n $$ For fixed $n$, since $0 \leqslant y_n \leqslant M_n$, then$$ f(n, m) = \sum_{k = 0}^{M_n} f(n - 1, m - k). $$ Note that the case where $n = 1$ is included. Further define$$ g(n, m) = \begin{cases} \sum\limits_{k = 0}^m f(n, k); & m \geqslant 0\\ 0; & m < 0 \end{cases}, $$ then$$ \begin{cases} f(n, m) = g(n - 1, m) - g(n - 1, m - M_n - 1)\\ g(n, m) = g(n, m - 1) + f(n, m) \end{cases}, \quad (n \geqslant 1,\ m \geqslant 0) $$ or$$ \begin{cases} f(n, m) = g(n - 1, m)\ (0 \leqslant m \leqslant M_n)\\ f(n, m) = g(n - 1, m) - g(n - 1, m - M_n - 1)\ (m > M_n)\\ g(n, 0) = 1\\ g(n, m) = g(n, m - 1) + f(n, m)\ (m \geqslant 1) \end{cases} $$

The code is showed below (with some optimization).

tmp = 0;
for(i = 1; i <= I; i++) {
    tmp += L[i];
    M[i] = (H[i] - L[i]) / S;
}
N = (T - tmp) / S;  //T' is renamed as N

sort(M);    //Ascending order

i_0 = 0;
while(!M[++i_0]);   //M[i] = 0 implies y[i] = 0

f[i_0 - 1][i_0 - 1] = 1;
for(i = i_0; i <= N; i++) f[i_0 - 1][i] = 0;
for(i = i_0; i <= N; i++) g[i_0 - 1][i] = 1;

for(i = i_0; i <= I; i++) {
    for(j = 0; j <= M[i] && j <= N; j++)
        f[i][j] = g[i - 1][j];
    for(j = M[i] + 1; j <= N; j++)
        f[i][j] = g[i - 1][j] - g[i - 1][j - M[i] - 1];

    g[i][0] = 1;
    for(j = 1; j <= N; j++)
        g[i][j] = g[i][j - 1] + f[i][j];
}

The time complexity is approximately $O(TIS^{-1})$.

Answer 2

Here we calculate OP's example using a generating function approach. Then we derive in a similar way a general formula from which the wanted number can be manually obtained at least for small values of $I$.

We consider $T=100, I=3, S=2$ and the pairs $$(L_j,H_j)\in\{(10,100),(20,80),(0,80)\}.$$

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series. We obtain

\begin{align*} \color{blue}{[x^{100}]}&\color{blue}{\left(x^{10}+x^{12}+\cdots+x^{100}\right)\left(x^{20}+x^{22}+\cdots+x^{80}\right)\left(x^0+x^2+\cdots+x^{80}\right)}\tag{1}\\ &=[x^{100}]x^{10}\left(\sum_{j=0}^{45}x^{2j}\right)x^{20}\left(\sum_{j=0}^{30}x^{2j}\right)\left(\sum_{j=0}^{40}x^{2j}\right)\tag{2}\\ &=[x^{70}]\frac{1-x^{92}}{1-x^2}\cdot\frac{1-x^{62}}{1-x^2}\cdot\frac{1-x^{82}}{1-x^2}\tag{3}\\ &=[x^{70}]\frac{1-x^{62}}{(1-x^2)^3}\tag{4}\\ &=[x^{70}]\left(1-x^{62}\right)\sum_{j=0}^\infty\binom{-3}{j}\left(-x^2\right)^j\tag{5}\\ &=\left([x^{70}]-[x^8]\right)\sum_{j=0}^{\infty}\binom{j+2}{2}x^{2j}\tag{6}\\ &=\binom{37}{2}-\binom{6}{2}\tag{7}\\ &\,\,\color{blue}{=651} \end{align*}

Comment:

• In (1) we encode for each of the three variables all possibilities in terms of generating functions.

• In (2) we factor out common terms and use the sigma symbol for a more compact notation.

• In (3) we apply the finite geometric series formula and we use the formula $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

• In (4) we calculate the numerator of (3) skipping all powers greater than $70$ since they do not contribute to $[x^{70}]$.

• In (5) we apply the binomial series expansion.

• In (6) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$. We use the linearity of the coefficient of operator and apply again the formula as we did in (3).

• In (7) we select the coefficients accordingly.

We now derive a general formula similarly as we did it in the concrete example above.

We obtain \begin{align*} \color{blue}{[x^T]}&\color{blue}{\prod_{j=1}^I\left(x^{L_j}+x^{L_j+S}+\cdots+x^{L_j+S\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}\right)}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^I\left(1+x^S+\cdots+x^{S\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}\right)\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^I\sum_{k=0}^{\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}x^{k\cdot S}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \frac{1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}}{1-x^S}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \left(1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}\right)\sum_{j=0}^\infty \binom{-I}{j}(-x)^S\\ &\,\,\color{blue}{=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \left(1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}\right)\sum_{j=0}^\infty\binom{I+j-1}{I-1}x^S} \end{align*} whereby the last line corresponds to (6).