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

Question

将若干个人(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，但这个只计算出方案数，没有输出具体方案

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

Answer 1

其实就是求组合，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;
        }
}