此题的难度在于如何去除重复的子集。因为C++里的set不接收vector作为元素,所以必须考虑其他办法。
此题的解法是:将nums排序。如果nums[i]!=nums[i-1]
,则按照一般的算法,将results里的所有N个数组都加入nums[i]并再放入results中。
如果nums[i]==nums[i-1]
,那么之前的方法可能会造成重复。比如说对于[1,2,2]的测试数据,第三轮中产生的[]+[2]和第二轮中已有的[2]就重复了。怎么办呢?对策是:不用把results里的所有元素都取出,而是只取之前一轮添加的数目。
比如对于[1,2,2,2]的测试数据。 初始:[] 第一轮:[],[1] (增加了一个元素) 第二轮:[],[1],[2],[1,2](增加了两个元素) 第三轮:[],[1],[2],[1,2],[2,2],[1,2,2](增加了两个) 因为第二轮我们只增加了两个元素,且nums[2]==nums[1],所以我们只取第二轮结果里的最后两个元素进行添加。 第四轮:[],[1],[2],[1,2],[2,2],[1,2,2],[2,2,2],[1,2,2,2](增加了两个) 因为第三轮我们只增加了两个元素,且nums[3]==nums[2],所以我们只取第三轮结果里的最后两个元素进行添加。
if (nums[i]!=nums[i-1])
{
add = results.size();
results.push_back(所有元素都取出加nums[i]再放回);
}
else if (nums[i]==nums[i-1])
{
results.push_back(最后add个元素取出加上nums[i]再放回);
}