[LeetCode] 每日一题 3343. 统计平衡排列的数目（动态规划 + 组合计数）

题目描述

给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。

请你返回 num 不同排列 中，平衡 字符串的数目。

由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

一个字符串的 排列 指的是将字符串中的字符打乱顺序后连接得到的字符串。

题目链接

https://leetcode.cn/problems/count-number-of-balanced-permutations

示例输入

示例 1

输入：num = "123"

输出：2

解释：

num 的不同排列包括： "123" ，"132" ，"213" ，"231" ，"312" 和 "321" 。
它们之中，"132" 和 "231" 是平衡的。所以答案为 2 。

示例 2

输入：num = "112"

输出：1

解释：

num 的不同排列包括："112" ，"121" 和 "211" 。
只有 "121" 是平衡的。所以答案为 1 。

示例 3

输入：num = "12345"

输出：0

解释：

num 的所有排列都是不平衡的。所以答案为 0 。

提示

• 2 <= num.length <= 80

• num 中的字符只包含数字 '0' 到 '9' 。

解题思路

这题初看起来像排列类问题，但加上“奇偶位下标之和相等”的条件后，难度陡然上升。我一开始没什么思路，最后是参考了题解的 动态规划 + 组合计数 解法，受益匪浅。

核心思想是将问题转化成一个“0-1 背包”风格的子集划分问题：我们要将每个数字合理分配到奇数位和偶数位上，使得两个位置上的数字和相等。

我们设状态 f[i][curr][oddCnt] 表示当前考虑数字 0~i，奇数位已经放了 oddCnt 个数字，其和为 curr 时的方案数。当前数字 i 的数量是 cnt[i]，我们尝试将其中 j 个放在奇数位，剩下的放在偶数位，用组合数计算放法，然后累加所有可行方案。

初始化方面，f[0][0][0] = 1 表示什么都没放的初始状态。最后我们统计奇数位有一半数字、和为总和一半的情况，即可得到答案。

这题虽然维度高，但可以通过合理剪枝、限制状态范围避免爆内存。同时，组合数预处理也大幅提升效率。

代码实现

class Solution {
    static final int MOD = 1000000007;

    public int countBalancedPermutations(String num) {
        int[] count = new int[10];
        int sum = 0;
        for (char c : num.toCharArray()) {
            count[c - '0']++;
            sum += c - '0';
        }
        if ((sum & 1) != 0) {
            return 0;
        }
        int target = sum / 2;
        int n = num.length();
        int maxOdd = (n + 1) / 2;
        long[][] comb = new long[maxOdd + 1][maxOdd + 1];
        long[][] f = new long[target + 1][maxOdd + 1];
        for (int i = 0; i <= maxOdd; i++) {
            comb[i][i] = 1;
            comb[i][0] = 1;
            for (int j = 1; j < i; j++) {
                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
            }
        }
        f[0][0] = 1;
        int temp = 0, total = 0;
        for (int i = 0; i < 10; i++) {
            temp += count[i];
            total += i * count[i];
            for (int oddCnt = Math.min(temp, maxOdd); oddCnt >= Math.max(0, temp - (n - maxOdd)); oddCnt--) {
                int evenCnt = temp - oddCnt;
                for (int curr = Math.min(total, target); curr >= Math.max(0, total - target); curr--) {
                    long res = 0;
                    for (int j = Math.max(0, count[i] - evenCnt); j <= Math.min(count[i], oddCnt) && i * j <= curr;
                         j++) {
                        long ways = comb[oddCnt][j] * comb[evenCnt][count[i] - j] % MOD;
                        res = (res + ways * f[curr - i * j][oddCnt - j] % MOD) % MOD;
                    }
                    f[curr][oddCnt] = res % MOD;
                }
            }
        }
        return (int)f[target][maxOdd];
    }
}

复杂度分析

• 时间复杂度：

  • 约为 O(10 sum n²)，其中 10 表示枚举数字 0~9，sum 是目标一半总和，n 是字符串长度。虽然看似复杂，但由于状态压缩和合理剪枝，实测在题目数据范围内表现良好 🚀

• 空间复杂度：

  • O(sum * n)，使用二维数组压缩一维状态，空间控制在可接受范围内 📦

总结

这题的核心在于建模能力，把排列转化为“子集划分 + 组合计数”的动态规划问题是关键。过程中涉及到的组合数计算、状态压缩技巧，对我这种日常刷一些算法题的开发者来说是一次很好的练手机会 👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。