题目重点：每条支出由payees均分，允许跨原始付款关系清算，输出全体清零的最少交易方案。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入payer、整数amount、非空且身份不重复的payees；payer可在或不在payees中，各payee均摊。
- 训练采用Fraction精确分摊，不编造无法整除时的最小货币单位舍入规则；若正式题要求整数金额，需先给余数分配合同。
- 允许任何欠者付给任意应收者，不要求沿原消费边；精确示例限制最多16个非零账户。
解题路线
- payer增加应收净额amount，每payee减amount/人数，零净额账户删除。总净额为0是必要不变量。
- 任意清算交易图的每个连通组件都必须零和；若有m个非零账户、g个组件，至少m−g条边。因此最大化可分成的零和组数，再每组用债权/欠款双指针清零，达到最少m−g。
- 枚举子集净和，用memo对剩余mask选含其首个账户的零和子组，避免组排列重复。精确求最大组数；重建组后配对付款。不把简单任意配对称全局最优。
手动走一遍
Alice付4000由Bob/Jess/Alice/Sam均分；Jess付2000由Jess/Alice均分。净额Alice+2000、Bob−1000、Sam−1000、Jess0，清算Bob→Alice1000、Sam→Alice1000，共2笔。净额[+5,+3,−3,−5]可分两个零和组，仅2笔；错误配对顺序可能做3笔，说明线性清算不保证最少。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from fractions import Fraction
from functools import lru_cache
def settle_expenses(expenses):
net=defaultdict(Fraction)
for payer,amount,payees in expenses:
if type(amount) is not int or amount<0 or not payees or len(payees)!=len(set(payees)):
raise ValueError("nonnegative integer amount and unique nonempty payees required")
share=Fraction(amount,len(payees))
net[payer]+=amount
for person in payees:net[person]-=share
people=[p for p in net if net[p]];balances=[net[p] for p in people];n=len(people)
if n>16:raise ValueError("exact training solver limited to 16 nonzero accounts")
sums=[Fraction(0)]*(1<<n)
for mask in range(1,1<<n):
bit=mask&-mask;sums[mask]=sums[mask^bit]+balances[bit.bit_length()-1]
choice={}
@lru_cache(None)
def groups(mask):
if not mask:return 0
first=mask&-mask;best=-1;sub=mask
while sub:
if sub&first and sums[sub]==0:
candidate=1+groups(mask^sub)
if candidate>best:best=candidate;choice[mask]=sub
sub=(sub-1)&mask
return best
full=(1<<n)-1;groups(full);payments=[]
while full:
group=choice[full];full^=group
credit=[[people[i],balances[i]] for i in range(n) if group>>i&1 and balances[i]>0]
debt=[[people[i],-balances[i]] for i in range(n) if group>>i&1 and balances[i]<0]
i=j=0
while i<len(credit) and j<len(debt):
amount=min(credit[i][1],debt[j][1]);payments.append((debt[j][0],credit[i][0],amount))
credit[i][1]-=amount;debt[j][1]-=amount
if not credit[i][1]:i+=1
if not debt[j][1]:j+=1
return payments
复杂度
m非零账户，子集净和O(2^m)，枚举剩余mask子组的保守O(3^m)时间，O(2^m+m)空间；Fraction位成本另计。大账户数需要明确只求可行方案或另选优化预算，不能承诺此精确法大规模可用。
易错点与追问
容易失分的边界
- 消费付款方向与清算方向相反：已垫付净正者收款，净负者付款。
- 以浮点判断零和可能误分组；不能未经约定四舍五入每份而破坏守恒。
- 至少m−1笔只是整体一组上界；多个独立零和组可以更少。
继续深挖
- 输出货币最小单位时余数如何公平分配，怎样保持每笔总额守恒？
- 限制付款关系或各笔有费用时，为什么零和分组证明不足？
