常规的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]本身也不应该被选中。否则的话,就违背了我们之前的指导方针:对于相同的元素我们不能跳跃着选取。