Finding all combinations that sum up to a specific number with given constrains 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.
 A: 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})$.
A: 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).

