i in even positions. To form a balanced permutation, we need to enumerate all valid assignments of digits such that the sum of digits in odd positions equals the sum in even positions.

We sequentially allocate digits (0) through (9) across odd and even positions:

Step 1 - Digit 0: Assign k_0 zeros to the m odd positions, leaving cnt[0] - k_0 zeros for the remaining (n - m) even positions. The number of such combinations is: $T_0 = \binom{m}{k_0} \cdot \binom{n-m}{cnt[0] - k_0}$
Step 2 - Digit 1: Assign (k_1) ones to the (m - k_0) remaining odd positions, leaving (cnt[1] - k_1) ones for (n-m-(cnt[0] - k_0)) even positions. The number of combinations is: $T_1 = \binom{m-k_0}{k_1} \cdot \binom{n-m-(cnt[0]-k_0)}{cnt[1]-k_1}$
General Step for Digit (i): Assign k_i occurrences of digit i to odd positions. The number of remaining odd positions is $m - \sum_{j=0}^{i-1} k_j$, and the number of remaining even positions is $n - m - \sum_{j=0}^{i-1}(cnt[j] - k_j)$. The number of arrangements for digit (i) is: $T_i = \binom{m-\sum_{j=0}^{i-1} k_j}{k_i} \cdot \binom{n-m-\sum_{j=0}^{i-1}(cnt[j]-k_j)}{cnt[i]-k_i}.$

The total number of balanced permutations, given a valid configuration $(k_0, ..., k_9)$, is: $$ T = \prod_{i=0}^{9} \binom{m-\sum_{j=0}^{i-1} k_j}{k_i} \cdot \binom{n-m-\sum_{j=0}^{i-1}(cnt[j]-k_j)}{cnt[i]-k_i} $$ Calculating this for all valid configurations ensures we count all balanced permutations.

To avoid redundant calculations, we employ a memoized search. Let:

dfs(i, curr, oddCnt) represent the number of valid ways to distribute digits from (i) to (9), where:
- (oddCnt) positions remain for odd indices,
- (curr) is the sum needed in odd positions.

Here is the DFS process:

For each digit (i), assign (j) copies to odd positions. The number of ways to choose these (j) positions is: $\binom{oddCnt}{j}$ The remaining cnt[i] - j copies are placed in even positions, with: $\sum_{k=i}^{9} cnt[k] - oddCnt$ slots available.
The combinations for this step are: $\binom{oddCnt}{j} \cdot \binom{\sum_{

Related Tags