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

x23hi9b5
• 5

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]]]

[[[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]]]

``````#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);
}
``````

1 个回答
✓ 已被采纳

`N = 6, K = 2`为例

``````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);
}``````

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进