Count Number of Balanced Permutations - Solution & Explanation
Problem Statement
You are given a string num. A string of digits is called balanced if the sum of the digits at even indices is equal to the sum of the digits at odd indices.
Return the number of distinct permutations of num that are balanced.
Since the answer may be very large, return it modulo 109 + 7.
A permutation is a rearrangement of all the characters of a string.
Example 1:
Input: num = "123"
Output: 2
Explanation:
- The distinct permutations of
numare"123","132","213","231","312"and"321". - Among them,
"132"and"231"are balanced. Thus, the answer is 2.
Example 2:
Input: num = "112"
Output: 1
Explanation:
- The distinct permutations of
numare"112","121", and"211". - Only
"121"is balanced. Thus, the answer is 1.
Example 3:
Input: num = "12345"
Output: 0
Explanation:
- None of the permutations of
numare balanced, so the answer is 0.
Constraints:
2 <= num.length <= 80numconsists of digits'0'to'9'only.
Approach Overview
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.
Approach 1: Brute Force Approach
This approach involves generating all distinct permutations of the string and then checking each permutation to determine if it is balanced. For a string of length n, generate all permutations and check if the sum of digits at even indices equals the sum of digits at odd indices.
The code uses Python's itertools.permutations to generate all unique permutations of the input string. For each permutation, it calculates sums of digits at even and odd indices and checks if they are equal. If they are, it counts the permutation as balanced. The final count is returned modulo 10^9 + 7.
Complexity
Time Complexity: O(n! * n), where n is the length of the string. Generating permutations takes O(n!) and checking each permutation takes O(n).
Space Complexity: O(n!) due to the storage of all permutations in the set.
Approach 2: Optimized Pre-computation Approach Using Backtracking
The optimized approach involves using backtracking to selectively generate permutations. The algorithm uses a recursive approach for swapping based on the feasibility of forming a balanced sum. It avoids generating all permutations explicitly, thereby reducing the complexity significantly.
The implementation involves backtracking with position tracking. It recursively estimates whether adding a digit at an even or odd position can lead to the required balance by adjusting sums dynamically. A frequency counter is used to ensure digits aren't reused.
Complexity
Time Complexity: O(n!), improved by pruning states early.
Space Complexity: O(n) due to recursion stack usage.
Approach 3: Memoization Search + Combinatorial Mathematics
First, we count the occurrences of each digit in the string num and record them in the array cnt, then calculate the total sum s of the string num.
If s is odd, then num cannot be balanced, so we directly return 0.
Next, we define a memoization search function dfs(i, j, a, b), where i represents the current digit to be filled, j represents the remaining sum of digits to be filled in odd positions, and a and b represent the remaining number of digits to be filled in odd and even positions, respectively. Let n be the length of the string num, then the answer is dfs(0, s / 2, n / 2, (n + 1) / 2).
In the function dfs(i, j, a, b), we first check if all digits have been filled. If so, we need to ensure that j = 0, a = 0, and b = 0. If these conditions are met, it means the current arrangement is balanced, so we return 1; otherwise, we return 0.
Next, we check if the remaining number of digits to be filled in odd positions a is 0 and j > 0. If so, it means the current arrangement is not balanced, so we return 0 early.
Otherwise, we can enumerate the number of current digits assigned to odd positions l, and the number of digits assigned to even positions is r = cnt[i] - l. We need to ensure 0 leq r leq b and l times i leq j. Then we calculate the number of current arrangements t = C_a^l times C_b^r times dfs(i + 1, j - l times i, a - l, b - r). Finally, the answer is the sum of all arrangement counts.
The time complexity is O(|\Sigma| times n^2 times (n + |\Sigma|)), where |\Sigma| represents the number of different digits, and in this problem |\Sigma| = 10. The space complexity is O(n^2 times |\Sigma|^2).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n! * n), where n is the length of the string. Generating permutations takes O(n!) and checking each permutation takes O(n). Space Complexity: O(n!) due to the storage of all permutations in the set. |
| Optimized Pre-computation Approach Using Backtracking | Time Complexity: O(n!), improved by pruning states early. Space Complexity: O(n) due to recursion stack usage. |
| Memoization Search + Combinatorial Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Check | O(n! * n) | O(n) | Useful only for very small strings or for understanding the definition of balanced permutations |
| Combinatorics + Backtracking with Pre-computation | O(10 * n * target) | O(n * target) | General solution for large inputs where permutations cannot be generated directly |
Video Solution
Count Number of Balanced Permutations | Super Detailed Explanation | Leetcode 3343 |codestorywithMIK • codestorywithMIK • 9,780 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Number of Balanced Permutations easy or hard?
Count Number of Balanced Permutations Python/Java solution
How to solve Count Number of Balanced Permutations in O(n)?
What is the best approach for Count Number of Balanced Permutations?
Is Count Number of Balanced Permutations asked at Google/Amazon/Meta?
What data structure is used in Count Number of Balanced Permutations?
What is the time complexity of Count Number of Balanced Permutations?
Ready to solve this problem?
Practice Count Number of Balanced Permutations with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor