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

常规的DFS。本题需要特别注意的是,如何高效地避免重复搜索。比如1 2 2 2 3,中间的三个相同的2,如果只取两个,其实有三种取法。这三种取法对应的subset其实都长得一样(.. 2 2 ...)。

去重的技巧就是:对于n个连续的相同元素,如果我们打算取k个,那么永远只取前k个。这样的话,DFS的代码可以写成:

for (int i=cur; i<nums.size(); i++)
{
  if (i>=1 && nums[i]==nums[i-1] && visited[i-1]==true)
    continue;
   ...
}

这段代码的意思是,如果nums[i]和它前面一个元素相同,但是前面一个元素并没有被选中,那么nums[i]本身也不应该被选中。否则的话,就违背了我们之前的指导方针:对于相同的元素我们不能跳跃着选取。