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

思路分析

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

TypeScript 代码

```typescript
const MX = 80;
const MOD = 10 ** 9 + 7;

// 预处理组合数 C[n][k]（帕斯卡三角）
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) {
        const d = +ch;
        cnt[d]++;
        s += d;
    }

    // 如果总和为奇数，无法平衡
    if (s % 2 !== 0) {
        return 0;
    }

    const n = num.length;
    const target = s / 2;
    const evenSlots = Math.floor(n / 2);      // 偶数位个数（索引 0,2,4...）
    const oddSlots = Math.floor((n + 1) / 2); // 奇数位个数（索引 1,3,5...）

    // 记忆化缓存（用 Record 实现，key 为 "i,j,a,b"）
    const memo: Record<string, number> = {};

    const dfs = (i: number, j: number, a: number, b: number): number => {
        // i: 当前处理的数字(0-9)
        // j: 偶数位还需要凑的和
        // a: 偶数位还剩下的空位
        // b: 奇数位还剩下的空位
        
        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 memo) {
            return memo[key];
        }

        let ans = 0;
        // 枚举当前数字 i 放到偶数位的个数 l
        for (let l = 0; l <= Math.min(cnt[i], a); l++) {
            const r = cnt[i] - l; // 放到奇数位的个数
            // 需要满足：奇数位放得下，且偶数位凑的和不超过目标
            if (r >= 0 && r <= b && l * i <= j) {
                // 从偶数位 a 个位置选 l 个放数字 i: C(a, l)
                // 从奇数位 b 个位置选 r 个放数字 i: C(b, r)
                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;
            }
        }

        memo[key] = ans;
        return ans;
    };

    return dfs(0, target, evenSlots, oddSlots);
}
```

核心思路说明

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

复杂度

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

参考来源

-  (Doocs LeetCode 官方题解，提供了标准 TypeScript 实现)
-  (Algo Monster，提供了带详细注释的 TypeScript 实现)

注意事项

1. BigInt 的使用：TypeScript 中 `number` 类型在计算组合数乘积时可能溢出，需要用 `BigInt` 进行中间计算，最后转回 `number`
2. 组合数预处理：使用帕斯卡三角在模块初始化时一次性预处理，避免重复计算
3. 记忆化 key：TypeScript 没有 Python 的 `@cache` 装饰器，需要手动用 `Record<string, number>` 实现，key 用字符串拼接
4. 偶数位/奇数位定义：索引从 0 开始，所以偶数位（索引 0,2,4...）个数是 `n/2`，奇数位（索引 1,3,5...）个数是 `(n+1)/2`