Lintcode18 Subsets II solution problem solution

[topic description]

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice:Each element in a subset must be in non-descending order.The ordering between two subsets is free.The solution set must not contain duplicate subsets.

Given a list of possible duplicate numbers, return all possible subsets

Note: each element in the subset is non-descending; the order between the two subsets is irrelevant; the solution set cannot contain duplicate subsets.

[topic link]

Http://www.lintcode.com/en/problem/subsets-ii/

[topic Analysis]

The classic DFS problem, if you have followed nine chapters of Weibo students should be quite familiar with this routine, the difference with the previous topic SubSet is that there is a repetition problem. How to solve it?

It's simple. Each time you choose a number, only the first repeated number is selected, not the later, so that there will be no duplicate set. Some students here must have asked, if you only choose the first one, how do you get the 222 combination? The answer is: don't think too much about recursion, just consider the current situation.

Example: 1 2 2 2 3 4

So the process of getting 22 / 2 is recursive in three layers, each layer only selects the first 2 at the beginning of the current index, so 22 / 2 can still be grouped out. And will not group repetition, because each level of recursion you do not consider repetition, this is fine.

Still remember the essence of recursion: just think about recursion at this level, don't think too much about it.

[answer link]

Https://www.jiuzhang.com/solutions/subsets-ii/