从0到21无放回选3个数，求和为3的倍数的选法总数

你的初始思路存在偏差：3的倍数各位数字之和为3的倍数是单个十进制正整数的整除判定规则，不适用于「三个不同整数求和后能被3整除」的场景，直接按整数模3的余数分类计算即可。

解题步骤 #

步骤1：按模3余数对0-21的整数分类 #

0到21共22个整数，按除以3的余数分为三类：

• 余数为0：{0,3,6,9,12,15,18,21}，共8个元素
• 余数为1：{1,4,7,10,13,16,19}，共7个元素
• 余数为2：{2,5,8,11,14,17,20}，共7个元素

步骤2：枚举满足和为3的倍数的组合类型 #

三个数之和模3等于0的情况只有两种：

1. 三个数的余数完全相同：三个余0/三个余1/三个余2，和模3均为0
2. 三个数的余数分别为0、1、2各一个：0+1+2=3，模3为0

步骤3：分别计算两类情况的组合数 #

组合数计算规则：从n个元素中选3个的无顺序选法记为C(n,3) = n*(n-1)*(n-2)/6

第一类：同余数组合

• 从8个余0的数选3个：C(8,3) = 8*7*6/6 = 56
• 从7个余1的数选3个：C(7,3) = 7*6*5/6 = 35
• 从7个余2的数选3个：C(7,3) = 35
  同余数组合总选法：56 + 35 + 35 = 126

第二类：余数各一组合

从三类中各选1个，选法为三类数量的乘积：
8 * 7 *7 = 392

步骤4：总选法求和 #

总选法 = 126 + 392 = 518

内容的提问来源于stack exchange，提问作者Hardik Soni