以下是 LeetCode 3343. 统计平衡排列的数目的 Python3 实现。这道题的核心思路是记忆化搜索 + 组合数学。

思路分析

- 平衡排列定义：偶数位（0,2,4...）数字之和等于奇数位（1,3,5...）数字之和
- 设字符串长度为 n，偶数位有 `(n+1)//2` 个，奇数位有 `n//2` 个
- 先统计每个数字出现次数，计算总和。如果总和为奇数，直接返回 0
- 目标：从每个数字的出现次数中，分配一部分到偶数位，一部分到奇数位，使得偶数位数字之和等于总和的一半

Python3 代码

```python
from functools import cache
from collections import Counter
from math import comb

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        @cache
        def dfs(i: int, j: int, a: int, b: int) -> int:
            # i: 当前处理的数字(0-9)
            # j: 偶数位还需要凑的和
            # a: 偶数位还剩下的空位
            # b: 奇数位还剩下的空位
            if i > 9:
                # 所有数字处理完毕，检查是否满足条件
                return (j | a | b) == 0
            if a == 0 and j:
                # 偶数位没位置了但还需要凑和，不可能
                return 0
            ans = 0
            # 枚举当前数字 i 放到偶数位的个数 l
            for l in range(min(cnt[i], a) + 1):
                r = cnt[i] - l  # 放到奇数位的个数
                # 需要满足：奇数位放得下，且偶数位凑的和不超过目标
                if 0 <= r <= b and l * i <= j:
                    # 从偶数位 a 个位置选 l 个放数字 i: C(a, l)
                    # 从奇数位 b 个位置选 r 个放数字 i: C(b, r)
                    t = comb(a, l) * comb(b, r) * dfs(i + 1, j - l * i, a - l, b - r)
                    ans = (ans + t) % mod
            return ans

        nums = list(map(int, num))
        s = sum(nums)
        if s % 2:
            return 0
        n = len(nums)
        mod = 10**9 + 7
        cnt = Counter(nums)
        return dfs(0, s // 2, n // 2, (n + 1) // 2)
```

核心思路说明

要点    说明    
状态定义    `dfs(i, j, a, b)` 表示处理到数字 `i` 时，偶数位还需凑 `j` 的和，还剩 `a` 个偶数位空位和 `b` 个奇数位空位    
转移    枚举数字 `i` 放到偶数位的个数 `l`，奇数位自动放 `cnt[i]-l` 个    
组合数    用 `C(a, l) * C(b, r)` 计算当前数字的放置方案数    
边界    处理完 0-9 所有数字后，检查 `j==0 and a==0 and b==0`    

复杂度

- 时间复杂度: O(10 \times n^2 \times (n + 10)) — 其中 10 是数字种类数
- 空间复杂度: O(10 \times n^2 \times (n/2+1)) — 记忆化数组大小

参考来源

-  (Doocs LeetCode 官方题解)
-  (Algo Monster 题解)