Problem Statement
leetcode problem link
Brute Force [LTE]
class Solution:
def generate_permutation(self, start, nums, list_permutations, N):
if start == N:
if nums not in list_permutations:
list_permutations.append(nums[:])
return
for i in range(start, N):
nums[i], nums[start] = nums[start], nums[i]
self.generate_permutation(start + 1, nums, list_permutations, N)
nums[i], nums[start] = nums[start], nums[i]
def countBalancedPermutations(self, num: str) -> int:
nums = [int(c) for c in num]
list_permutations = []
N = len(nums)
self.generate_permutation(0, nums, list_permutations, N)
MOD = 10 ** 9 + 7
res = 0
for permutation in list_permutations:
even = 0
odd = 0
for i, v in enumerate(permutation):
if i % 2:
odd += v
else:
even += v
if odd == even:
res += 1
return res % MOD
Editorial
Approach 1: Memoization Search
class Solution:
def countBalancedPermutations(self, num: str) -> int:
MOD = 10**9 + 7
num = list(map(int, num))
tot = sum(num)
if tot % 2 != 0:
return 0
target = tot // 2
cnt = Counter(num)
n = len(num)
maxOdd = (n + 1) // 2
psum = [0] * 11
for i in range(9, -1, -1):
psum[i] = psum[i + 1] + cnt[i]
@cache
def dfs(pos, curr, oddCnt):
# If the remaining positions cannot complete a legal placement, or the sum of the elements in the current odd positions is greater than the target value
if oddCnt < 0 or psum[pos] < oddCnt or curr > target:
return 0
if pos > 9:
return int(curr == target and oddCnt == 0)
evenCnt = (
psum[pos] - oddCnt
) # Even-numbered positions remaining to be filled
res = 0
for i in range(
max(0, cnt[pos] - evenCnt), min(cnt[pos], oddCnt) + 1
):
# Place i of the current number at odd positions, and cnt[pos] - i at even positions
ways = comb(oddCnt, i) * comb(evenCnt, cnt[pos] - i) % MOD
res += ways * dfs(pos + 1, curr + i * pos, oddCnt - i)
return res % MOD
return dfs(0, 0, maxOdd)
Approach 2: Dynamic Programming
class Solution:
def countBalancedPermutations(self, num: str) -> int:
MOD = 10**9 + 7
tot, n = 0, len(num)
cnt = [0] * 10
for ch in num:
d = int(ch)
cnt[d] += 1
tot += d
if tot % 2 != 0:
return 0
target = tot // 2
max_odd = (n + 1) // 2
f = [[0] * (max_odd + 1) for _ in range(target + 1)]
f[0][0] = 1
psum = tot_sum = 0
for i in range(10):
# Sum of the number of the first i digits
psum += cnt[i]
# Sum of the first i numbers
tot_sum += i * cnt[i]
for odd_cnt in range(
min(psum, max_odd), max(0, psum - (n - max_odd)) - 1, -1
):
# The number of bits that need to be filled in even numbered positions
even_cnt = psum - odd_cnt
for curr in range(
min(tot_sum, target), max(0, tot_sum - target) - 1, -1
):
res = 0
for j in range(
max(0, cnt[i] - even_cnt), min(cnt[i], odd_cnt) + 1
):
if i * j > curr:
break
# The current digit is filled with j positions at odd positions, and cnt[i] - j positions at even positions
ways = (
comb(odd_cnt, j) * comb(even_cnt, cnt[i] - j) % MOD
)
res = (
res + ways * f[curr - i * j][odd_cnt - j] % MOD
) % MOD
f[curr][odd_cnt] = res % MOD
return f[target][max_odd]
