本文准备讲解1个算法编程问题, 这个算法编程问题来自LeetCode平台。不了解.LeetCode平台的读者可以阅读笔者文章(在线编程平台推荐-LeetCode)。问题的英文版本描述如下:
Subsets II
Given a collection of integers that might contain duplicates,nums, return all possible subsets.
Note:The solution set must not contain duplicate subsets.
For example,
Ifnums=[1,2,2], a solution is:
[ ]
[2],
[1],
[1,2,2],
[2,2],
[1,2],
问题的中文版本描述:
重复元素子集
给定一个可能含有重复数字的列表,返回其所有可能的子集
注意事项
子集中的每个元素都是非降序的
两个子集间的顺序是无关紧要的
解集中不能包含重复子集
样例
如果 S =[1,2,2],一个可能的答案为:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
该题目要求找出对应目标数据集的所有可能子集。例如对应数据集 [1,2,2],所有的可能子集共有6个。不含任何数据的空集有1个,含有1个数据的子集有2个,含有2个数据的子集有2个,含有3个数据的子集有1个。核心的算法为:先找数据量最多的子集,再找数据量次多的子集;并依次接续寻找对子集。例如对应数据集 [1,2,2],先找含有3个数据的子集,接着找含有2个数据的子集,接着找含有1个数据的子集。如何由前层子集找后层子集:对应 [1,2,2],移除首个数据得到 [2,2], 移除第2个数据得到 [1,2], 移除后个数据得到 [1,2]。算法要求删除所有重复子集。
核心算法部分内容见下图: