1. NP完全问题
集合划分是NP完全问题之一。
NP完全问题（NP-Complete）是非常困难的问题，目前没有找到哪怕一个多项式算法可以在有限的时间内解决这个问题。尽管如此，我们只需要依赖于指数时间的算法来求解NP完全问题，由于指数时间算法的复杂度极高，我们很难用它解决大规模的问题。
2. 集合划分问题介绍
集合划分问题是一个典型的组合优化问题，它的目标是将给定的集合划分成若干互不相交的子集，使得这些子集的并集可以表示原集合。集合划分问题的数学表述如下：
假设有一个集合S，其中包含了n个元素，那么它的该问题可以定义为：是否可以将S分成k个互不相交的子集S1、S2、.....、Sk，使得每个子集Si的元素个数之和相等？
3. 集合划分的运算复杂度
集合划分问题是一个NP完全问题，属于组合优化问题，时间复杂度较高。其中，交流复杂度可以用PCP等价问题描述。集合划分问题的背包变种被称为“多重背包问题”（Multi-dimensional Knapsack），该问题可以通过集合划分问题的算法进行求解。
4. 集合划分问题的算法设计
对于组合优化问题，我们通常采用的解题方法是枚举，也就是确定问题的所有可行解，再从中找到最优解。集合划分问题的暴力枚举算法是：从原集合S中选取若干个元素构成集合M，不断寻找集合M的所有可行子集，判断每一个子集能否被划分为k个相等大小的集合，找到满足条件的最优集合为止。
但是，上述暴力枚举算法的时间复杂度为O（2^n），根据指数时间的复杂度特点，随着集合元素数量的增加，运算时间会快速增加，长时间运行的效果将会很差。
因此，我们需要更高效的算法实现集合划分问题，其中一个比较成功的算法是回溯法。
回溯法的基本思路是：从集合S中选定若干个数，先判断选定的数能否被划分为k个集合，如果可以，就继续选定更多数，否则开始回溯，即返回上一个状态，进行其他选择来试图找到更优解。回溯法的时间复杂度上界是指数级别的。
下面是集合划分问题的基于回溯法的c++实现代码：
const int maxn = 20; // n ≤ 17 比较理想
int n, a[maxn], vis[maxn], tot = 0;
bool dfs(int x, int pos, int sum, int avg) { // x代表当前的子集编号，pos代表当前枚举到a的下标，sum为当前子集的元素和，avg为平均分
if(x == tot + 1) return true; // 如果已经划分完于K个子集，返回true，原序列可被划分
if(sum > avg) return false; // 如果当前子集的元素和大于平均分，说明不能加下一个元素了，返回false，回溯
if(sum == avg) return dfs(x + 1, 1, 0, avg); // 如果当前子集的元素和等于平均分，枚举下一个子集
//否则就是sum小于平均数的情况，可以加入下一个元素，尝试DFS下去
for(int i = pos; i <= n; ++i) {
if(!vis[i]) {
vis[i] = x; //标记当前元素属于x子集
if(dfs(x, i + 1, sum + a[i], avg)) return true; //枚举下一个元素
vis[i] = 0; //回溯
}
else continue;
}
return false;
}
int main() {
int k;
while(scanf("%d", &k) && k) {
memset(vis, 0, sizeof(vis));
int sum = 0; tot = 0;
//输入n和k组成的序列
for(int i = 1; i <= k; ++i) {
scanf("%d", &a[i]);
sum += a[i];
}
int avg = sum / k;
tot = k; //划分成k个子集
if(dfs(1, 1, 0, avg)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
5. 总结
集合划分问题是NP完全问题之一，总体难度很大，但可以采用回溯法等高效的算法实现。为了更好地解决这个问题，可以引入其平均分的计算方法，并在选择下一个子集时进行判断，在符合条件时才进行下一步的运算。