C++:动态规划之分组问题所有解

将若干个人(A,B,C,D,E,F,G……)分成若干队，每队人数可以是1、2或者3人。已知n，求组队详细方案

例：有3个人，方案有5个，分别是全部单独组队方案{A,B,C} , 单独组队与双人组队方案{A,BC} {AB,C} {AC,B}以及三人组队方案{ABC}

我知道求出组合的话用动态规划算法有类似，就是这个https://blog.csdn.net/zongjiaxiao/article/details/53223642，但这个只计算出方案数，没有输出具体方案

希望各位能够给个代码或者给个思路谢谢

其实就是求组合，C(n,1),c(n,2),c(n,3)，跟动态规划没啥关系

#include <iostream>
#include <vector>
using namespace std;
class project {
        void combin(vector<char> team, int pos, int n, vector<char>& item) {
                int size = team.size();
                if (n == 0) {
                        res.push_back(item);
                        return;
                }
                for (int i = pos; i < size; i++) {
                        item.push_back(team[i]);
                        combin(team, i + 1, n - 1, item);
                        item.pop_back();
                }
        }
public:
        vector<vector<char>> res;
        void getresult(vector<char> vecteam, int size) {
                vector<char> tmp;
                combin(vecteam, 0, size, tmp);
                
        }
};
int main()
{

        vector<char> team{ 'A','B','C' };
        project p;
        p.getresult(team, 1);
        p.getresult(team, 2);
        p.getresult(team, 3);
        for (auto v : p.res) {
                for (auto c : v) {
                        cout << c << " ";
                }
                cout << endl;
        }
}

在你算方案数的时候其实已经算出了答案了

我觉得这个问题可以分几步来做。
首先考虑这么一种最简单的情形，假设有n个人，分解后每一队有且只有k个人，且n是k的倍数即n=pk。
这种情况下有多少种分组方案呢？
应该有C(n,k)C(n-k,k)C(n-2k,k)...C(2k,k)C(k,k)/p!
然后我们考虑这样一个方程式
n=1K1+2K2+3K3，
这个方程当然有好多解。对于其中的一组有效解K1,K2,K3，可以做如下分配：
先在n人中挑选出K1个人（这样的选法有C(n,K1)种）进行一人一组的分配。对于挑选好的每一种K1的集合，都有C(K1,1)C(K1-1,1)...C(1,1)/K1!=1种分配方案。
所以共有A(K1,K2,K3)=C(n,K1)种方案。
再在剩下的n-K1人中挑选出2K2个人(这样的选法有C(n-K1,2K2)种)进行2人一组的分配。对于挑选好的每一种K2的集合，都有C(n-K1,2)C(n-K1-2,2)...C(2,2)/K2!种分配方案
所以共有B(K1,K2,K3)=C(n-K1,2K2)C(n-K1,2)C(n-K1-2,2)...C(2,2)/K2!种方案。
最后在剩下的n-K1-2K2人中挑选3K3(呃不用挑选了，剩下的都是)进行3人一组的分配，对于挑选好的每一种K3的集合，都有C(n-K1-2K2,3)C(n-K1-2K2-3,3)...C(3,3)/K3!种分配方案。
所以共有C(K1,K2,K3)=C(n-K1-2K2,3)C(n-K1-2K2-3,3)*...*C(3,3)/K3!种方案。

所以我的方案是，先求出n=1K1+2K2+3*K3的所有整数解，然后对于每一种整数解，依次去就A,B,C这3个函数，最后把每一种的A * B * C加起来就好了