如何实现这样的集合划分？

Question

比如：
输入
partitions([1, 2, 3, 4, 5, 6], 3)
返回

[[[1,2,3],[4,5,6]], [[1,2,4],[3,5,6]], [[1,2,5],[3,4,6]], [[1,2,6],[3,4,5]],
[[1,3,4],[2,5,6]], [[1,3,5],[2,4,6]], [[1,3,6],[2,4,5]], [[1,4,5],[2,3,6]],
[[1,4,6],[2,3,5]], [[1,5,6],[2,3,4]]]

输入 partitions([1, 2, 3, 4, 5, 6], 2)

返回

[[[1,2],[3,4],[5,6]], [[1,2],[3,5],[4,6]], [[1,2],[3,6],[4,5]], [[1,3],[2,4],[5,6]],
[[1,3],[2,5],[4,6]], [[1,3],[2,6],[4,5]], [[1,4],[2,3],[5,6]], [[1,4],[2,5],[3,6]],
[[1,4],[2,6],[3,5]], [[1,5],[2,3],[4,6]], [[1,5],[2,4],[3,6]], [[1,5],[2,6],[3,4]],
[[1,6],[2,3],[4,5]], [[1,6],[2,4],[3,5]], [[1,6],[2,5],[3,4]]]

相关问题：algorithm-for-computing-partitions-of-a-set-of-n-elements-into-subsets-of-size-m

目前想到的是，先生成[1, 2, 3, 4, 5, 6] choose 2的子集，然后再生成choose 3的子集，再选取交集为空的部分，感觉效率不高，有没有比较好的算法呢？
网上找到了一个类似的代码需要修改，但不知道那个递归函数怎么改

#include <iostream>
#include <vector>

using namespace std;

// arr: Store input array
// i: Stores current index of arr
// N: Stores length of arr
// K: Stores count of subsets
// nos: Stores count of feasible subsets formed
// v: Store K subsets of the given array

int counter = 0;

void print(vector<vector<int>> &vec) {
    for (int x = 0; x < vec.size(); x++) {
        cout << "{ ";
        for (int y = 0; y < vec[x].size(); y++) {
            cout << vec[x][y];
            cout << (y == vec[x].size() - 1 ? " " : ", ");
        }
        cout << (x == vec.size() - 1 ? "}" : "}, ");
    }
    cout << endl;
}

void PartitionSub(int arr[], int i, int N, int K, int nos, vector<vector<int>> &vec) {
    if (i >= N) {
        if (nos == K) {
            print(vec);
            counter++;
        }
        return;
    }
    for (int j = 0; j < K; j++) {
        if (vec[j].size() > 0) {
            vec[j].push_back(arr[i]);
            PartitionSub(arr, i + 1, N, K, nos, vec);
            vec[j].pop_back();
        } else {
            vec[j].push_back(arr[i]);
            PartitionSub(arr, i + 1, N, K, nos + 1, vec);
            vec[j].pop_back();
            break;
        }
    }
}

void partKSubsets(int arr[], int N, int K) {
    vector<vector<int>> v(K);
    if (K == 0 || K > N) {
        cout << "Not Possible" << endl;
    } else {
        cout << "The Subset Combinations are: " << endl;
        PartitionSub(arr, 0, N, K, 0, v);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
    partKSubsets(arr, N, K);
    printf("count = %d\n", counter);
}

Answer 1

以N = 6, K = 2为例

结果数组长度为3，递归每一个数时，依次往这3个数组里追加，数组满了就跳过，此外如果当前前一个数组还是空的，就不考虑后面的数组了。

void print(int n, int k, int ans[][k]) {
    for (int i = 0; i < n / k; ++i) {
        printf("{ ");
        for (int j = 0; j < k; ++j) {
            printf("%d%s", ans[i][j], j + 1 < k ? ", " : "");
        }
        printf(" }%s", i + 1 < n / k ? ", " : "\n");
    }
}
void dfs(const int arr[], int n, int k, int cur, int ans[][k], int len[]) {
    if (cur == n) print(n, k, ans);

    for (int i = 0; i < n / k; ++i) {
        if (len[i] == k) continue;
        ans[i][len[i]++] = arr[cur];
        dfs(arr, n, k, cur + 1, ans, len);
        if (!--len[i]) break;
    }
}
int main(int argc, char *argv[]) {
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 3;

    int ans[N / K][K], len[N / K];
    memset(len, 0, sizeof(len));
    dfs(arr, N, K, 0, ans, len);
}