Count Number of Balanced Permutations - Video Solutions

Problem Overview: Given a string of digits, count how many distinct permutations produce a balanced arrangement where the sum of digits at even indices equals the sum at odd indices. Because digits can repeat, the solution must account for duplicate permutations while ensuring the two index groups produce identical sums.

Approach 1: Brute Force Permutation Check (O(n! * n) time, O(n) space)

Generate every permutation of the string and verify whether it is balanced. For each permutation, iterate through the digits and accumulate two sums: one for even indices and one for odd indices. If the sums match, increment the result counter. Duplicate digits make this even slower because many permutations represent the same arrangement unless deduplicated with a set or frequency map. This method quickly becomes infeasible once the length grows beyond 9–10 characters, but it clearly demonstrates the definition of a balanced permutation.

Approach 2: Combinatorics + Backtracking with Pre-computation (O(10 * n * target) time, O(n * target) space)

A more scalable solution treats the problem as distributing digits into even and odd index groups. First compute the total digit sum. If it is odd, a balanced permutation cannot exist because both sides must sum to total / 2. Let evenSlots and oddSlots represent how many positions belong to each parity index. Count the frequency of each digit (0–9) and backtrack over digits deciding how many copies go into even positions. While exploring assignments, track two constraints: the number of used slots and the accumulated sum toward the target.

Pre-compute factorials and modular inverses to calculate permutations using multinomial coefficients. Once a valid distribution of digits across even slots reaches the required sum, the number of permutations for both sides can be computed using combinations of remaining frequencies. This converts the exponential permutation search into a bounded state search over digit counts and sums.

The key insight is that permutations are determined by how many copies of each digit go into each index group, not by the exact ordering during exploration. Pre-computation of factorials enables fast combinatorial counting, while the constrained backtracking prunes states that exceed slot limits or target sum.

Recommended for interviews: Start by describing the brute force permutation idea to demonstrate understanding of the definition. Then move to the combinatorics-based solution. Interviewers expect you to reduce the problem to digit frequency distribution, apply counting formulas, and use techniques from combinatorics, dynamic programming, and math to avoid enumerating permutations explicitly.