请教一道字节面试的题

有两种类型的物品集合A和B，每个集合内同一种物品的数量可能重复，但不会有物品同属两种类型。现在需要摆放这些物品，第一个物品需要是A类的，相同类型的物品不能摆放在一起，问总共有多少种摆放方式？

比如说 A= {1,2} B= {3,4}


可以摆放为 1 3 2 4, 1 4 2 3, 2 3 1 4, 2 4 1 3四种，所以返回4
又比如说 A = {1, 1} B = {2,2}
只可以摆放为 1 2 1 2， 所以返回1

先拆分：总排列＝所有A类排列方式*所有B类排列方式

对于其中某一类（比如A），统计每种物品出现的次数，化简成排列组合问题。比如，A种有3个1，4个2，其可能排列方式为 A77/(A33 × A44)

请指教：）

杨幂的老公 发表于 2020-3-17 02:08
comb(A) * comb(B)

不愧是杨幂老公

前面都提到了，分别计算A和B的组合数，具体怎么算，可以参考leetcode47. Permutations II，一般是用回溯算。