Lintcode17 Subsets solution problem solution

[topic description]

Given a set of distinct integers, return all possible subsets.

Notice:Elements in a subset must be in non-descending order;The solution set must not contain duplicate subsets.

Given a set of different integers, return all its subsets

Note: the arrangement of elements in a subset must be non-descending, and the solution set must not contain a duplicate subset.

[topic link]

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

[topic Analysis]

The subset class problem is similar to Combination, which is analyzed by the input array [1, 2, 3]. According to the meaning of the topic, the elements of the subset class returned finally should be arranged in ascending order, so the original array needs to be sorted first. The second requirement of the topic is that the subset can not be repeated, so the original problem is transformed into a combinatorial problem in mathematics. We first try to use DFS to solve the problem, and the approximate steps are as follows:

[1]-> [1,2]-> [1,2,3]

[2]-> [2,3]

[3]

Converting the above process into code is called logarithmic array traversal, and each round saves the previous results and adds them to the final return result in turn.

[answer link]

Http://www.jiuzhang.com/solution/subsets/