Skip to content

Latest commit

 

History

History
 
 

090.Subsets-II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

090.Subsets-II

此题的难度在于如何去除重复的子集。因为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]再放回);
}

Leetcode Link