python实现：数组所有子集的求解（国新日能笔试编程题）问题解题思路python具体实现题外记深浅拷贝代码实现示范

81 阅读 0 评论 54 点赞

我是靠谱客的博主积极汉堡，最近开发中收集的这篇文章主要介绍python实现：数组所有子集的求解（国新日能笔试编程题）问题解题思路python具体实现题外记深浅拷贝代码实现示范，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题

解题思路

python具体实现

题外记

深浅拷贝代码实现示范

问题

已知数组如X=[1,2,3,4],输出其所有的子集，如[1],[2],[3],[4],[1,2],[2,3],[3,4],[1,2,3],[2,3,4],[1,2,3,4]......

解题思路

分析：这其实也是一道找寻规律的问题。我们看子集的构成方式，就以X=[1,2,3,4]为例，首先空集[]是所有数组的子集，下面，我们先来第一个元素1，子集就是[],[1]；再来第二个元素2，子集就是[],[1],[2],[1,2]；再来第三个元素3，子集就是[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]；最后来第四个元素4，子集就是 [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4].至此，就得到了X所有的子集。注意看标红的数字所在的集合和前面的区别：即就在原来子集合的基础上，加进去新来的元素。

详细步骤如下：

1）初始化存储子集的变量result。初始化值为[[]]。

2）数组进行遍历，得到子集。如分析所示，容易发现，需要设置两层循环，外层用来遍历数组的元素，里层则是在当前的子集结果中，再新添上遍历到的元素，加入各个子集的结果

3）结果输出。上述遍历结束，子集也就得到了，输出即可。

python具体实现

def getArraySubSet(originArray):
    """
    :type originArray:list
    :rtype :listlist
    """
    result = [[]]
    for i in range(len(originArray)):
        for j in range(len(result)): 
            result.append(result[j]+[originArray[i]]) #现有每个子集中添加新元素，作为新子集加入结果集中
    return result

# 测试
originArray=[1,2,3,4]
subset = getArraySubSet(originArray) 
print(subset)

题外记

题目本身的思路和步骤没有什么问题，但在实现的时候，需要特别注意程序的深拷贝和浅拷贝的问题。上面的程序没有涉及到关于深浅拷贝的问题，因为考虑使用深拷贝的方式代码看起来不如上面简单明了。另外注意到的一个问题是：列表使用append()添加元素后，并不会有返回值，例如：a = [2],若c=a.ppend(3)，c的结果是None。刚开始自己代码实现出来的时候，检查逻辑是对的，但结果特别让自己意外，对深拷贝和浅拷贝的问题，这是第一次正式深刻认识到。

一点简单实用的总结：

copy.copy对于可变类型（列表、字典），会进行浅拷贝。
copy.copy对于不可变类型（元祖、数字、字符串），不会拷贝，仅仅是指向。
基本上只要不是我们自已手动调用的deepcopy方法都是浅拷贝。

不仅要掌握正确的方法，还要对错误的原因，去学会研究反思，从犯错中得到的学习，或许印象更深刻，成长的也更快！

深浅拷贝代码实现示范

1) 使用的浅拷贝的代码如下（结果错误）：

def getArraySubSet(originArray):
    if len(originArray)==0:
        return [[]]
    
    result = [[]]
    for i in range(len(originArray)):
        temp = result.copy()          #浅拷贝
        for j in range(len(result)): 
            temp[j].append(originArray[i])
        result = result + temp
    return result

# 测试
originArray=[1,2,3,4]
subset = getArraySubSet(originArray) 
print(subset)

2) 使用深拷贝的代码（需要借助模块copy）（结果正确）：

import copy    #导入copy模块，需要deepcopy()函数
def getArraySubSet(originArray):
    if len(originArray)==0:
        return [[]]
    
    result = [[]]
    for i in range(len(originArray)):
        temp = copy.deepcopy(result)   # 深拷贝
        for j in range(len(result)): 
            temp[j].append(originArray[i])
        result = result + temp
    return result

# 测试
originArray=[1,2,3,4]
subset = getArraySubSet(originArray) 
print(subset)

3）程序实例的结果：