问题
给出一个数组，比如 {1,2,3,4}，请求出数组的所有子集（1）？给出一个存在重复元素的数组，比如 {1,2,2,3,4}，请求出数组的所有子集（2）？请求出所有子集并且不允许出现重复子集（3）？
准备方法
////// 列表深拷贝/// public static ListClone (this List source){ List newList = new List (source.Count); foreach (var item in source) { newList.Add(item); } return newList;}
////// 比较两个列表是否等同，不考虑列表元素的顺序/// 比如 {1,2,3,4}与{2,1,4,3}比较返回true. {2,3}与{1,2}比较返回false/// public static bool EqualsList(this List source, List dest) where T : IEquatable { if (source.Count != dest.Count) return false; for (int i = 0; i < source.Count; i++) { if (source.Count(item => item.Equals(source[i])) != dest.Count(item => item.Equals(source[i]))) return false; } return true;}
////// 目标列表是否包含于源列表集合中，不考虑列表元素顺序/// public static bool ContainList(this List
> source, List destList) where T : IEquatable { for (int i = 0; i < source.Count; i++) { List sourceList = source[i]; if (sourceList.EqualsList(destList)) return true; } return false;}
递归解法
////// 获取集合的所有子集/// /// 源数组集合/// 是否允许重复子集/// 可选参数（默认1），初始分割长度（数组右侧）///public static List
> GetSubList (T[] source, bool allowRepeat, int rightSplitLength = 1) where T : IEquatable { // 返回子集集合 List
> rSet = new List
>(); // 数组长度为length int length = source.Length; // 递归基准情形，当数组长度为1时，子集为数组本身 if (length == 1) { rSet.Add(source.ToList ()); } else { // 左侧数组 T[] leftArray = source.Where((r, index) => index < length - rightSplitLength).ToArray(); // 右侧数组 T[] rightArray = source.Where((r, index) => index >= length - rightSplitLength).ToArray(); // 递归计算左侧数组子集集合 List
> leftSubSet = GetSubList(leftArray, allowRepeat); // 递归计算右侧数组子集集合 List
> rightSubSet = GetSubList(rightArray, allowRepeat); if (allowRepeat) { // A.左侧子集作为源数组子集 允许重复 rSet.AddRange(leftSubSet); // B.右侧子集作为源数组子集 允许重复 rSet.AddRange(rightSubSet); } else { // A.左侧子集作为源数组子集 不允许重复 foreach (var lefttemp in leftSubSet) { if (!rSet.ContainList(lefttemp)) { rSet.Add(lefttemp); } } // B.右侧子集作为源数组子集 不允许重复 foreach (var righttemp in rightSubSet) { if (!rSet.ContainList(righttemp)) { rSet.Add(righttemp); } } } // 左右侧子集合并集 List
> combineSubSet = new List
>(); foreach (var leftSubList in leftSubSet) { foreach (var rightSubList in rightSubSet) { // 左右侧集合项交叉合并 List combineList = new List (); combineList.AddRange(leftSubList.Clone ()); combineList.AddRange(rightSubList.Clone ()); combineSubSet.Add(combineList); } } if (allowRepeat) { // C.左右侧子集合并集，形成源数组子集 允许重复 rSet.AddRange(combineSubSet); } else { // C.左右侧子集合并集，形成源数组子集 不允许重复 foreach (var combinetemp in combineSubSet) { if (!rSet.ContainList(combinetemp)) { rSet.Add(combinetemp); } } } } return rSet;}
测试结果
输入1）{1,2,3,4}结果：
输入2）{1,2,2,3,4}允许重复，结果：
输入3）{1,2,2,3,4} 不允许重复，结果：
非递归解法
{1，2，3，，，，N-1，N} 集合子集表示为f(N)
将数组进行拆分
f(N-1) = {1，2，3，，，，N-1} ，f(1) = {N}
很显然，问题已经拆分为具有相同情况的子问题
{1} => {1}
{1，2} => {1}，{2} => {1}+{2}+{1，2}
很容易推出 f(N) 的子集为 f(N-1) + f(1) + COMBINE(f(N-1),f(1))(取笛卡尔并集)
代码如下（此处去掉了重复子集判断）：
public static List
> GetSubList2 (T[] source) where T : IEquatable { List
> rList = new List
>(); for (int i = 0; i < source.Length; i++) { List
> combineList = new List
>(); foreach (var list in rList) { List tmpList = list.Clone(); tmpList.Add(source[i]); combineList.Add(tmpList); } rList.AddRange(combineList); rList.Add(new List () { source[i] }); } return rList;}
另一种非递归解法
根据数学知识，很容易知道，N个元素的子集个数为2^N - 1，时间复杂度是指数级的，我们可以联想到位操作（比如位移就是2的指数级操作），我们用0和1为下标，标识每一个元素是否出现在子集中，因此可以如此标识子集 (此处比如N为5)
1（00001）,2（00010），3（00011），，，，，31（11111）
我们可以发现，从1到2^N-1的十进制循环数据中，每一个数据的二进制位对应的下标的数据集合就是所有子集
代码如下：
public static void PrintSubList(T[] source){ int length = source.Length; int loopCount = 1 << length; int subCount = 0; for (int i = 1; i < loopCount; i++) { int takeNumber = i; for (int bitIndex = 0; bitIndex < length; bitIndex++) { if ((takeNumber & 1) == 1) { Console.Write(" {0} ", source[bitIndex]); } takeNumber >>= 1; } Console.WriteLine(); subCount++; } Console.WriteLine("共有 {0} 个子集.", subCount);}
延伸题目
给定一个数t，以及n个整数，在这n个整数中找到相加之和为t的所有组合，例如t = 4，n = 6，这6个数为[4, 3, 2, 2, 1, 1]，这样输出就有4个不同的组合，它们的相加之和为4：4, 3+1, 2+2, and 2+1+1。请设计一个高效算法实现这个需求
使用上述方法对此方法进行求解，代码如下：
////// 获取集合的所有子集，要求集合内元素相加之和为sum /// public static List> GetSubList4Sum(List source, int sum){ // 返回子集集合 List
> rSet = new List
>(); // 数组长度为length int length = source.Count; for (int i = length - 1; i >= 0; i--) { // 选取右侧数据 int rightNum = source[i]; // 获取左侧集合 List leftList = source.Where((r, index) => index < i).ToList(); if (rightNum > sum) { continue; } else if (rightNum == sum) { List rightList = new List () { rightNum }; // 避免重复 2 if (!rSet.ContainList(rightList)) { rSet.Add(rightList); } } else { List
> leftSet = GetSubList4Sum(leftList, sum - rightNum); foreach (var leftAvail in leftSet) { List combineList = new List (); combineList.AddRange(leftAvail); combineList.Add(rightNum); if (!rSet.ContainList(combineList)) { rSet.Add(combineList); } } } } return rSet;}
结语
其实，这些题目是以前做过的题目，并且以前还发过博客，最近突然想把那些做过的题目找回来，重新做了一遍，温故而知新