问题

给出一个数组，比如 {1,2,3,4}，请求出数组的所有子集（1）？给出一个存在重复元素的数组，比如 {1,2,2,3,4}，请求出数组的所有子集（2）？请求出所有子集并且不允许出现重复子集（3）？

准备方法

/// <summary>/// 列表深拷贝/// </summary>public static List<T> Clone<T>(this List<T> source){    List<T> newList = new List<T>(source.Count);    foreach (var item in source)    {        newList.Add(item);    }    return newList;}

/// <summary>/// 比较两个列表是否等同，不考虑列表元素的顺序/// 比如 {1,2,3,4}与{2,1,4,3}比较返回true. {2,3}与{1,2}比较返回false/// </summary>public static bool EqualsList<T>(this List<T> source, List<T> dest)    where T : IEquatable<T>{    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;}

/// <summary>/// 目标列表是否包含于源列表集合中，不考虑列表元素顺序/// </summary>public static bool ContainList<T>(this List<List<T>> source, List<T> destList)    where T : IEquatable<T>{    for (int i = 0; i < source.Count; i++)    {        List<T> sourceList = source[i];        if (sourceList.EqualsList(destList)) return true;    }    return false;}

递归解法

/// <summary>/// 获取集合的所有子集/// </summary>/// <param name="source">源数组集合</param>/// <param name="allowRepeat">是否允许重复子集</param>/// <param name="rightSplitLength">可选参数（默认1），初始分割长度（数组右侧）</param>/// <returns></returns>public static List<List<T>> GetSubList<T>(T[] source, bool allowRepeat, int rightSplitLength = 1)    where T : IEquatable<T>{    // 返回子集集合    List<List<T>> rSet = new List<List<T>>();    // 数组长度为length    int length = source.Length;    // 递归基准情形，当数组长度为1时，子集为数组本身    if (length == 1)    {        rSet.Add(source.ToList<T>());    }    else    {        // 左侧数组        T[] leftArray = source.Where((r, index) => index < length - rightSplitLength).ToArray();        // 右侧数组        T[] rightArray = source.Where((r, index) => index >= length - rightSplitLength).ToArray();        // 递归计算左侧数组子集集合        List<List<T>> leftSubSet = GetSubList(leftArray, allowRepeat);        // 递归计算右侧数组子集集合        List<List<T>> 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<List<T>> combineSubSet = new List<List<T>>();        foreach (var leftSubList in leftSubSet)        {            foreach (var rightSubList in rightSubSet)            {                // 左右侧集合项交叉合并                List<T> combineList = new List<T>();                combineList.AddRange(leftSubList.Clone<T>());                combineList.AddRange(rightSubList.Clone<T>());                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<List<T>> GetSubList2<T>(T[] source)    where T : IEquatable<T>{    List<List<T>> rList = new List<List<T>>();    for (int i = 0; i < source.Length; i++)    {        List<List<T>> combineList = new List<List<T>>();        foreach (var list in rList)        {            List<T> tmpList = list.Clone();            tmpList.Add(source[i]);            combineList.Add(tmpList);        }        rList.AddRange(combineList);        rList.Add(new List<T>() { 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>(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。请设计一个高效算法实现这个需求

使用上述方法对此方法进行求解，代码如下：

/// <summary> /// 获取集合的所有子集，要求集合内元素相加之和为sum /// </summary> public static List<List<int>> GetSubList4Sum(List<int> source, int sum){    // 返回子集集合     List<List<int>> rSet = new List<List<int>>();    // 数组长度为length     int length = source.Count;    for (int i = length - 1; i >= 0; i--)    {        // 选取右侧数据         int rightNum = source[i];        // 获取左侧集合         List<int> leftList = source.Where((r, index) => index < i).ToList();        if (rightNum > sum)        {            continue;        }        else if (rightNum == sum)        {            List<int> rightList = new List<int>() { rightNum };            // 避免重复 2            if (!rSet.ContainList(rightList))            {                rSet.Add(rightList);            }        }        else        {            List<List<int>> leftSet = GetSubList4Sum(leftList, sum - rightNum);            foreach (var leftAvail in leftSet)            {                List<int> combineList = new List<int>();                combineList.AddRange(leftAvail);                combineList.Add(rightNum);                if (!rSet.ContainList(combineList))                {                    rSet.Add(combineList);                }            }        }    }    return rSet;}

结语

其实，这些题目是以前做过的题目，并且以前还发过博客，最近突然想把那些做过的题目找回来，重新做了一遍，温故而知新

编程拾趣--集合子集问题