LeetCode 0090. Subsets II子集II【Python】

Python015

LeetCode 0090. Subsets II子集II【Python】,第1张

LeetCode

Given a collection of integers that might contain duplicates, nums , return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

力扣

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明： 解集不能包含重复的子集。

示例:

回溯

Python

难度：★★★☆☆

类型：数组

方法：动态规划

力扣链接请移步 本题传送门

更多力扣中等题的解决方案请移步 力扣中等题目录

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输出： True

说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

提示：

1 <= k <= len(nums) <= 16

0 <nums[i] <10000

这道题我们采用类似动态规划的方法来做。但是这道题的做法和以前的动态规划不同。

输入数组为nums，先判断特殊情况，我们先求得数组中元素和划分为k个包的平均数，如果元素和不能被k整除，或者存在任意一个元素大于平均数，则不能满足题目的要求的划分方式。这个是显而易见的。

我们用一个二进制数字来表示nums中的元素被选中或者未被选中，用数字表达的好处是节省空间，定义函数helper，函数的输入有两个：

current_state：当前各个数字的选择状态，用二进制数表达，1代表选中，0代表未选中；

current_sum：当前选中的数字的和。

函数的输入方式实际上规定了一种选择方式，函数的返回值为在当前选择方式下，能否实现题目要求的划分。

函数完成以下功能：

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步 力扣中等题解析

数组允许进行批量操作而无需使用for循环，因此更加简便，这种特性也被称为向量化。任何两个等尺寸之间的算术操作都应用逐元素操作的方式进行。

同尺度数组之间的比较，会产生一个布尔型数组。

上述操作均是在同尺度数组之间进行的，对于不同尺度数组间的操作，会使用到广播特性。

索引：获取数组中特定位置元素的过程；

切片：获取数组元素子集的过程。

new_a = a.astype(new_type)

astype()方法一定会创建新的数组（原始数据的一个拷贝），即使两个类型一致。

ls = a.tolist()

转置是一种特殊的数据重组形式，可以返回底层数据的视图而不需要复制任何内容。

数组拥有 transpose 方法，也有特殊的 T 属性。

对于更高纬度的数组， transpose 方法可以接受包含轴编号的元组，用于转置轴。

ndarray的 swapaxes 方法，通过接受一对轴编号作为参数，并对轴进行调整用于重组数据。

swapaxes 方法返回的是数据的视图，而没有对数据进行复制。

Reference：

《Python for Data Analysis:Data Wrangling with Pandas,Numpy,and IPython》