Count Number of Balanced Permutations solution and explanation
Google
9 more videos on this problem
Count Number of Balanced Permutations | Super Detailed Explanation | Leetcode 3343 |codestorywithMIKcodestorywithMIK · 1:16:59 · 9K views
Count Number of Balanced Permutations | Leetcode 3343Techdose · 51:11 · 4K views
3343. Count Number of Balanced Permutations | Leetcode Daily - PythonLeetcode Daily · 8:55 · 3K views
3343. Count Number of Balanced Permutations | Solving UNCUT with Explanations 🔥 09-05-25LeetCode Daily LIVE · 1:17:05 · 1K views
3343. Count Number of Balanced Permutations || Leetcode Daily Challenge || DP || CombinatoricsEye on AI and DSA · 19:50 · 1K views
Daily Leetcode #1865: May 09, 2025 - 3343. Count Number of Balanced PermutationsProgramming Live with Larry · 1:14:25 · 1K views
3343. Count Number of Balanced Permutations (Leetcode Hard)Programming Live with Larry · 52:55 · 1K views
Leetcode 3343 | Count Number Of Balanced Permutations | Leetcode Daily QuestionCoding Grower · 32:47 · 956 views
Leetcode 3343. Count the Number of Balanced PermutationsExpertFunda · 35:51 · 698 views
Count Number of Balanced Permutations - Leetcode 3343ThinkOutsideTheBox · 28:49 · 650 views
The problem
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.
from itertools import permutations
def count_balanced_permutations(num):
mod = 10**9 + 7
num_set = set(permutations(num))
count = 0
for perm in num_set:
even_sum = 0
odd_sum = 0
for i, digit in enumerate(perm):
if i % 2 == 0:
even_sum += int(digit)
else:
odd_sum += int(digit)
if even_sum == odd_sum:
count += 1
return count % mod
# Example Usage:
# num = "123"
# print(count_balanced_permutations(num)) # Output: 2import java.util.HashSet;
import java.util.Set;
public class BalancedPermutations {
private static final int MOD = 1000000007;
private static boolean isBalanced(String perm) {
int evenSum = 0, oddSum = 0;
for (int i = 0; i < perm.length(); i++) {
if (i % 2 == 0) evenSum += perm.charAt(i) - '0';
else oddSum += perm.charAt(i) - '0';
}
return evenSum == oddSum;
}
public static int countBalancedPermutations(String num) {
Set<String> permutations = new HashSet<>();
permute(num.toCharArray(), 0, num.length() - 1, permutations);
int count = 0;
for (String perm : permutations) {
if (isBalanced(perm)) {
count = (count + 1) % MOD;
}
}
return count;
}
private static void permute(char[] arr, int l, int r, Set<String> permutations) {
if (l == r) {
permutations.add(new String(arr));
} else {
for (int i = l; i <= r; i++) {
swap(arr, l, i);
permute(arr, l + 1, r, permutations);
swap(arr, l, i);
}
}
}
private static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
String num = "123";
System.out.println(countBalancedPermutations(num)); // Output: 2
}
}#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
#define MOD 1000000007
bool isBalanced(const std::string& num) {
int even_sum = 0, odd_sum = 0;
for (size_t i = 0; i < num.size(); i++) {
if (i % 2 == 0) even_sum += num[i] - '0';
else odd_sum += num[i] - '0';
}
return even_sum == odd_sum;
}
int count_balanced_permutations(std::string num) {
std::sort(num.begin(), num.end());
std::unordered_set<std::string> permutations;
int count = 0;
do {
if (isBalanced(num)) {
count = (count + 1) % MOD;
}
} while (std::next_permutation(num.begin(), num.end()));
return count;
}
int main() {
std::string num = "123";
std::cout << count_balanced_permutations(num) << std::endl; // Output: 2
return 0;
}function isBalanced(num) {
let evenSum = 0, oddSum = 0;
for (let i = 0; i < num.length; i++) {
if (i % 2 === 0)
evenSum += parseInt(num[i]);
else
oddSum += parseInt(num[i]);
}
return evenSum === oddSum;
}
function permute(arr, l, r, set) {
if (l === r) {
set.add(arr.join(''));
} else {
for (let i = l; i <= r; i++) {
[arr[l], arr[i]] = [arr[i], arr[l]];
permute(arr, l + 1, r, set);
[arr[l], arr[i]] = [arr[i], arr[l]];
}
}
}
function countBalancedPermutations(num) {
const numArray = num.split('');
const permutations = new Set();
const mod = 1e9 + 7;
permute(numArray, 0, num.length - 1, permutations);
let count = 0;
for (let perm of permutations) {
if (isBalanced(perm)) {
count = (count + 1) % mod;
}
}
return count;
}
// Example usage:
// let num = "123";
// console.log(countBalancedPermutations(num)); // Output: 2#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MOD 1000000007
void swap(char* a, char* b) {
char temp = *a;
*a = *b;
*b = temp;
}
bool isBalanced(const char* num) {
int even_sum = 0, odd_sum = 0;
for (int i = 0; num[i]; i++) {
if (i % 2 == 0) even_sum += num[i] - '0';
else odd_sum += num[i] - '0';
}
return even_sum == odd_sum;
}
void permute(char* num, int l, int r, int* count) {
if (l == r) {
if (isBalanced(num)) {
*count = (*count + 1) % MOD;
}
return;
}
for (int i = l; i <= r; i++) {
swap(&num[l], &num[i]);
permute(num, l + 1, r, count);
swap(&num[l], &num[i]);
}
}
int count_balanced_permutations(const char* num) {
int n = strlen(num);
char* mutable_num = malloc((n + 1) * sizeof(char));
strcpy(mutable_num, num);
int count = 0;
permute(mutable_num, 0, n - 1, &count);
free(mutable_num);
return count;
}
int main() {
char num[] = "123";
printf("%d\n", count_balanced_permutations(num)); // Output: 2
return 0;
}using System;
using System.Collections.Generic;
class BalancedPermutations {
private const int MOD = 1000000007;
static bool IsBalanced(string num) {
int evenSum = 0, oddSum = 0;
for (int i = 0; i < num.Length; i++) {
if (i % 2 == 0) evenSum += num[i] - '0';
else oddSum += num[i] - '0';
}
return evenSum == oddSum;
}
public static int CountBalancedPermutations(string num) {
HashSet<string> permutations = new HashSet<string>();
Permute(num.ToCharArray(), 0, num.Length - 1, permutations);
int count = 0;
foreach (var perm in permutations) {
if (IsBalanced(perm)) {
count = (count + 1) % MOD;
}
}
return count;
}
static void Permute(char[] arr, int l, int r, HashSet<string> permutations) {
if (l == r) {
permutations.Add(new string(arr));
} else {
for (int i = l; i <= r; i++) {
Swap(ref arr[l], ref arr[i]);
Permute(arr, l + 1, r, permutations);
Swap(ref arr[l], ref arr[i]);
}
}
}
static void Swap(ref char a, ref char b) {
char temp = a;
a = b;
b = temp;
}
static void Main() {
string num = "123";
Console.WriteLine(CountBalancedPermutations(num)); // Output: 2
}
}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.
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.
def count_balanced_permutations(num):
MOD = 10**9 + 7
def backtrack(freq, pos, odd_sum, even_sum):
if pos == len(num):
return 1 if odd_sum == even_sum else 0
count = 0
for digit in freq:
if freq[digit] > 0:
freq[digit] -= 1
if pos % 2 == 0:
count += backtrack(freq, pos + 1, odd_sum, even_sum + int(digit))
else:
count += backtrack(freq, pos + 1, odd_sum + int(digit), even_sum)
freq[digit] += 1
return count
from collections import Counter
freq = Counter(num)
result = backtrack(freq, 0, 0, 0)
return result % MOD
# Example Usage:
# num = "123"
# print(count_balanced_permutations(num)) # Output: 2import java.util.HashMap;
import java.util.Map;
public class BalancedPermutations {
private static final int MOD = 1000000007;
private static int backtrack(Map<Integer, Integer> freq, int pos, int odd_sum, int even_sum, int total) {
if (pos == total) {
return odd_sum == even_sum ? 1 : 0;
}
int count = 0;
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() > 0) {
entry.setValue(entry.getValue() - 1);
if (pos % 2 == 0) {
count += backtrack(freq, pos + 1, odd_sum, even_sum + entry.getKey(), total);
} else {
count += backtrack(freq, pos + 1, odd_sum + entry.getKey(), even_sum, total);
}
entry.setValue(entry.getValue() + 1);
}
}
return count % MOD;
}
public static int countBalancedPermutations(String num) {
Map<Integer, Integer> freq = new HashMap<>();
for (char c : num.toCharArray()) {
freq.put(c - '0', freq.getOrDefault(c - '0', 0) + 1);
}
return backtrack(freq, 0, 0, 0, num.length());
}
public static void main(String[] args) {
String num = "123";
System.out.println(countBalancedPermutations(num)); // Output: 2
}
}#include <iostream>
#include <unordered_map>
#define MOD 1000000007
int backtrack(std::unordered_map<int, int>& freq, int pos, int odd_sum, int even_sum, int total) {
if (pos == total) {
return odd_sum == even_sum ? 1 : 0;
}
int count = 0;
for (auto& [digit, count] : freq) {
if (count > 0) {
freq[digit]--;
if (pos % 2 == 0) {
count += backtrack(freq, pos + 1, odd_sum, even_sum + digit, total);
} else {
count += backtrack(freq, pos + 1, odd_sum + digit, even_sum, total);
}
freq[digit]++;
}
}
return count % MOD;
}
int countBalancedPermutations(const std::string& num) {
std::unordered_map<int, int> freq;
for (char c : num) {
freq[c - '0']++;
}
return backtrack(freq, 0, 0, 0, num.size());
}
int main() {
std::string num = "123";
std::cout << countBalancedPermutations(num) << std::endl; // Output: 2
return 0;
}function backtrack(pos, oddSum, evenSum, total, freq) {
if (pos === total) {
return oddSum === evenSum ? 1 : 0;
}
let count = 0;
for (let digit of Object.keys(freq)) {
if (freq[digit] > 0) {
freq[digit] -= 1;
count += (pos % 2 === 0 ? backtrack(pos + 1, oddSum, evenSum + Number(digit), total, freq)
: backtrack(pos + 1, oddSum + Number(digit), evenSum, total, freq));
count %= 1e9 + 7;
freq[digit] += 1;
}
}
return count;
}
function countBalancedPermutations(num) {
let freq = {};
for (let digit of num) {
freq[digit] = (freq[digit] || 0) + 1;
}
return backtrack(0, 0, 0, num.length, freq);
}
// Example usage:
// let num = "123";
// console.log(countBalancedPermutations(num)); // Output: 2#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int backtrack(int* freq, int len, int pos, int odd_sum, int even_sum, int total) {
if (pos == total) {
return odd_sum == even_sum ? 1 : 0;
}
int count = 0;
for (int i = 0; i < 10; i++) {
if (freq[i] > 0) {
freq[i]--;
count = (count % MOD +
(pos % 2 == 0 ? backtrack(freq, len, pos + 1, odd_sum, even_sum + i, total)
: backtrack(freq, len, pos + 1, odd_sum + i, even_sum, total))) % MOD;
freq[i]++;
}
}
return count;
}
int count_balanced_permutations(const char* num) {
int freq[10] = {0};
int n = strlen(num);
for (int i = 0; i < n; i++) {
freq[num[i] - '0']++;
}
return backtrack(freq, 10, 0, 0, 0, n);
}
int main() {
char num[] = "123";
printf("%d\n", count_balanced_permutations(num)); // Output: 2
return 0;
}using System;
using System.Collections.Generic;
class BalancedPermutations {
private const int MOD = 1000000007;
static int Backtrack(Dictionary<int, int> freq, int pos, int oddSum, int evenSum, int total) {
if (pos == total) {
return oddSum == evenSum ? 1 : 0;
}
int count = 0;
foreach (var digit in freq.Keys) {
if (freq[digit] > 0) {
freq[digit]--;
count = (count +
(pos % 2 == 0 ? Backtrack(freq, pos + 1, oddSum, evenSum + digit, total)
: Backtrack(freq, pos + 1, oddSum + digit, evenSum, total))) % MOD;
freq[digit]++;
}
}
return count;
}
public static int CountBalancedPermutations(string num) {
var freq = new Dictionary<int, int>();
foreach (char c in num) {
int digit = c - '0';
if (!freq.ContainsKey(digit)) {
freq[digit] = 0;
}
freq[digit]++;
}
return Backtrack(freq, 0, 0, 0, num.Length);
}
static void Main() {
string num = "123";
Console.WriteLine(CountBalancedPermutations(num)); // Output: 2
}
}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.
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).
const MX = 80;
const MOD = 10 ** 9 + 7;
const c: number[][] = Array.from({ length: MX }, () => Array(MX).fill(0));
(function init() {
c[0][0] = 1;
for (let i = 1; i < MX; i++) {
c[i][0] = 1;
for (let j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
})();
function countBalancedPermutations(num: string): number {
const cnt = Array(10).fill(0);
let s = 0;
for (const ch of num) {
cnt[+ch]++;
s += +ch;
}
if (s % 2 !== 0) {
return 0;
}
const n = num.length;
const m = Math.floor(n / 2) + 1;
const f: Record<string, number> = {};
const dfs = (i: number, j: number, a: number, b: number): number => {
if (i > 9) {
return (j | a | b) === 0 ? 1 : 0;
}
if (a === 0 && j > 0) {
return 0;
}
const key = `${i},${j},${a},${b}`;
if (key in f) {
return f[key];
}
let ans = 0;
for (let l = 0; l <= Math.min(cnt[i], a); l++) {
const r = cnt[i] - l;
if (r >= 0 && r <= b && l * i <= j) {
const t = Number(
(((BigInt(c[a][l]) * BigInt(c[b][r])) % BigInt(MOD)) *
BigInt(dfs(i + 1, j - l * i, a - l, b - r))) %
BigInt(MOD),
);
ans = (ans + t) % MOD;
}
}
f[key] = ans;
return ans;
};
return dfs(0, s / 2, Math.floor(n / 2), Math.floor((n + 1) / 2));
}const (
MX = 80
MOD = 1_000_000_007
)
var c [MX][MX]int
func init() {
c[0][0] = 1
for i := 1; i < MX; i++ {
c[i][0] = 1
for j := 1; j <= i; j++ {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD
}
}
}
func countBalancedPermutations(num string) int {
var cnt [10]int
s := 0
for _, ch := range num {
cnt[ch-'0']++
s += int(ch - '0')
}
if s%2 != 0 {
return 0
}
n := len(num)
m := n/2 + 1
f := make([][][][]int, 10)
for i := range f {
f[i] = make([][][]int, s/2+1)
for j := range f[i] {
f[i][j] = make([][]int, m)
for k := range f[i][j] {
f[i][j][k] = make([]int, m+1)
for l := range f[i][j][k] {
f[i][j][k][l] = -1
}
}
}
}
var dfs func(i, j, a, b int) int
dfs = func(i, j, a, b int) int {
if i > 9 {
if j == 0 && a == 0 && b == 0 {
return 1
}
return 0
}
if a == 0 && j > 0 {
return 0
}
if f[i][j][a][b] != -1 {
return f[i][j][a][b]
}
ans := 0
for l := 0; l <= min(cnt[i], a); l++ {
r := cnt[i] - l
if r >= 0 && r <= b && l*i <= j {
t := c[a][l] * c[b][r] % MOD * dfs(i+1, j-l*i, a-l, b-r) % MOD
ans = (ans + t) % MOD
}
}
f[i][j][a][b] = ans
return ans
}
return dfs(0, s/2, n/2, (n+1)/2)
}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 | – |
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 |
Frequently asked questions
Is Count Number of Balanced Permutations easy or hard?
Count Number of Balanced Permutations is classified as a Hard problem because it combines multiple concepts: combinatorics, permutation counting with duplicates, and constrained dynamic programming. The challenge lies in recognizing that you should count digit distributions instead of enumerating permutations.
Count Number of Balanced Permutations Python/Java solution
Python and Java implementations typically compute digit frequencies, precompute factorials with modular inverses, and then perform backtracking or DP to distribute digits into even slots while maintaining the required sum. Once a valid configuration is found, multinomial combinations count the permutations. The same logic translates cleanly to C++ and other languages.
How to solve Count Number of Balanced Permutations in O(n)?
A strict O(n) solution is not typical because the algorithm must consider digit frequencies and sum constraints. The practical optimal approach uses combinatorics plus dynamic programming or backtracking over digits, leading to about O(10 * n * target) complexity. Precomputing factorials allows constant-time combination calculations during counting.
What is the best approach for Count Number of Balanced Permutations?
The most efficient approach uses combinatorics with constrained backtracking and factorial pre-computation. Instead of generating permutations, you distribute digit frequencies between even and odd index slots while tracking the required half sum. Valid distributions are counted using multinomial coefficients. This reduces the search space dramatically compared to brute force.
Is Count Number of Balanced Permutations asked at Google/Amazon/Meta?
Problems involving permutation counting, digit frequency distribution, and combinatorics frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test whether candidates can convert brute force permutation enumeration into a combinatorial counting problem using math and dynamic programming.
What data structure is used in Count Number of Balanced Permutations?
The solution mainly uses a frequency array for digits (size 10), recursion or dynamic programming for exploring distributions, and factorial arrays for combinatorial calculations. These structures help track digit counts, slot usage, and the target sum efficiently.
What is the time complexity of Count Number of Balanced Permutations?
The optimized solution runs in roughly O(10 * n * target) time where target is half of the total digit sum. The algorithm iterates over digit frequencies and explores valid distributions while pruning impossible states. Space complexity is O(n * target) for memoization or DP states.