我在算法面试中遇到了一个无法解决的问题。问题是：
给定一个长度为n的数组，其中n是偶数，将数组中的元素重新组合为两个较小的数组，每个数组的长度相等(n/2(，条件是这些较小数组的总和相等。如果无法实现，请返回-1。
例如。输入：[1,1,1,2,3,3,6]输出：[[1,1,2,6]，[1,3,3]]
Eg。输入：[1,4,5,6]输出：-1
我想随机初始化两个子数组，然后交换两个元素，使它们的差异至少是两个数组总和中总差异的一半。然而，当输入是非法的时，我很难想出一个标准来决定场景，答案应该是-1。
感谢您的帮助和提示！
好的，我将在这里发布我的愚蠢解决方案。我计算出所有可能的子序列，其和等于总和的一半。然后，检查是否有长度等于数组长度一半的子序列。
如果有人提出更快的解决方案，请告诉我：(
from collections import Counter
def partition(nums):
if sum(nums) % 2 != 0: # if the sum is an odd number it's impossible
return -1
nums.sort()
target = sum(nums) / 2
out = []
ct = Counter(nums)
def dp(cand): # first find out all the sub-sequence with sum equal to n/2
if sum(cand) == target:
out.append(cand)
remain = target - sum(cand)
for i, number in enumerate(nums):
if number > remain:
break
if (cand and number < cand[-1]) or ct[number] == 0:
continue
if i >= 1 and nums[i - 1] == nums[i]:
continue
ct[number] -= 1
dp([*cand, number])
ct[number] += 1
dp([])
for sub_array in out:
if len(sub_array) != len(nums) / 2:
continue # check if there is any subsequence with exactly half length
another_array = []
stats = Counter(sub_array)
for num, count in ct.items():
another_array += [num] * (count - stats[num])
return [another_array, sub_array]
return -1
let sum=0;
for (int i=0;i<x.length;i++)
{sum=sum+i}
if (sum%2!=0){
return - 1;}
else {
//do your code here //
}
如果数组的和不等于偶数，则返回-1。希望这能解决你的问题