Python算法题集

Python算法题集_子集

题78：子集
1. 示例说明
2. 题目解析
- - 题意分解
- - 优化思路
- - 测量工具
3. 代码展开
- 1) 标准求解【递归】
- 2) 改进版一【双层下标循环】
- 3) 改进版二【双层枚举循环】
- 4) 改进版三【双层下标循环+位运算】
- 5) 改进版四【单行双层循环+位运算】
- 6) 改进版五【高效迭代模块】
4. 最优算法
5. 相关资源

本文为Python算法题集之一的代码示例

题78：子集

1. 示例说明

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
```
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```
示例 2：
```
输入：nums = [0]
输出：[[],[0]]
```
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同

2. 题目解析

- 题意分解

本题是计算整数集合的全子集
基本的设计思路为从空集逐步增加元素到整数全集，可以用递归实现

- 优化思路

通常优化：减少循环层次
通常优化：增加分支，减少计算集
通常优化：减少内存使用量，减少独立变量数量
通常优化：采用内置算法、专业模块来提升计算速度
分析题目特点，分析最优解
1. 可以将每次增加元素后的结果集，用枚举方式遍历
2. 可以考虑用0/1的位运算来标记元素是否放入结果集中
3. 可以考虑用高效迭代模块单元itertools

- 测量工具

本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
本题本地化超时测试用例自己生成，详见章节【最优算法】，代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【递归】

使用递归合成子集

页面功能测试，性能卓越，超过98% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_base(self, nums):result = []ilen = len(nums)def dfs_subset(iPos, tmp):result.append(tmp)for jIdx in range(iPos, ilen):dfs_subset(jIdx + 1, tmp + [nums[jIdx]])dfs_subset(0, [])return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_base, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_base 的运行时间为 869.20 ms；内存使用量为 159380.00 KB 执行结果 = 1048576

2) 改进版一【双层下标循环】

下标遍历结果集，使用双层循环合成子集

页面功能测试，勉强通关，超过17% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_ext1(self, nums):result=[[]]ilen=len(nums)for iIdx in range(ilen):for jIdx in range(len(result)):result.append(result[jIdx]+[nums[iIdx]])return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_ext1 的运行时间为 738.17 ms；内存使用量为 157248.00 KB 执行结果 = 1048576

3) 改进版二【双层枚举循环】

枚举遍历结果集，使用双层循环合成子集

页面功能测试，性能卓越，超越95% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_ext2(self, nums):result = [[]]for aInt in nums:result = result + [[aInt] + num for num in result]return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_ext1 的运行时间为 738.17 ms；内存使用量为 157248.00 KB 执行结果 = 1048576

4) 改进版三【双层下标循环+位运算】

双层下标循环，通过位运算合成子集

页面功能测试，马马虎虎，超过58% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_ext3(self, nums):result = []for iIdx in range(1 << len(nums)):tmp = []for jIdx in range(len(nums)):if iIdx & 1 << jIdx:tmp.append(nums[jIdx])result.append(tmp)return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_ext3, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_ext3 的运行时间为 2970.67 ms；内存使用量为 190108.00 KB 执行结果 = 1048576

5) 改进版四【单行双层循环+位运算】

双层循环一行代码，通过位运算合成子集，减少了中间变量

页面功能测试，性能优良，超过86% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_ext4(self, nums):ilen = len(nums)return [[nums[jIdx] for jIdx in range(ilen) if iIdx & (1 << jIdx)] for iIdx in range(1 << ilen)]aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_ext4, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_ext4 的运行时间为 2622.59 ms；内存使用量为 190936.00 KB 执行结果 = 1048576

6) 改进版五【高效迭代模块】

使用高效迭代模块itertools来合成子集

页面功能测试，马马虎虎，超过58% 在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def subsets_ext5(self, nums):import itertoolsresult = []for iIdx in range(len(nums) + 1):result += [tmp for tmp in itertools.combinations(nums, iIdx)]return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 subsets_ext5 的运行时间为 115.02 ms；内存使用量为 139632.00 KB 执行结果 = 1048576

4. 最优算法

根据本地日志分析，最优算法为第6种方式【高效迭代模块】subsets_ext5

本题测试数据，似乎能推出以下结论：

枚举循环性能优于下标循环
itertool模块应该是用C等语言实现，效率远高于Python代码逐行实现

nums = [x for x in range(20)]
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.subsets_base, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.subsets_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.subsets_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.subsets_ext3, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.subsets_ext4, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.subsets_ext5, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 算法本地速度实测比较
函数 subsets_base 的运行时间为 869.20 ms；内存使用量为 159380.00 KB 执行结果 = 1048576
函数 subsets_ext1 的运行时间为 738.17 ms；内存使用量为 157248.00 KB 执行结果 = 1048576
函数 subsets_ext2 的运行时间为 560.14 ms；内存使用量为 156068.00 KB 执行结果 = 1048576
函数 subsets_ext3 的运行时间为 2970.67 ms；内存使用量为 190108.00 KB 执行结果 = 1048576
函数 subsets_ext4 的运行时间为 2622.59 ms；内存使用量为 190936.00 KB 执行结果 = 1048576
函数 subsets_ext5 的运行时间为 115.02 ms；内存使用量为 139632.00 KB 执行结果 = 1048576