Leetcode hot topic Hot 100 day 33: "subset"

Continue to brush LeetCode Hot topic HOT 100 The subject of , And update my blog solutions. stay csdn In my blog, I will try to explain clearly in words , relevant Java Code, you can go to my Personal blog jinhuaiyu.com View in .
subject ： A subset of
Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.
Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .
Example 1：
Input ：nums = [1,2,3]
Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2：
Input ：nums = [0]
Output ：[[],[0]]
Tips ：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums All elements in Different from each other

solution 1： Dynamic programming
We need to find the former i The set of all subsets of digits and the first i+1 The relationship between sets of all subsets of digits . Suppose the set of the former is f(i), Add numbers to each subset nums[i+1] Form a set add, be f(i+1) Namely f(i)+add. You can try this set rule by yourself .
In limine , We need to put an empty set in the set （ An empty set is a subset of all sets ）, And then from 0 To traverse the nums Array , Start calculating layer by layer f(i). In each layer, the set obtained from the previous layer is copied and added with numbers nums[i], Then put back the collection .

solution 2： Binary corresponding subset
For all subsets , All individually correspond to one nums Array every take and don't take , Assume that 1 Do not take as 0, about nums by {5,2,9}, Subset empty set corresponds to binary number 000, A subset of {5,2} Corresponding to binary number 110. Altogether 2^n A subset of , It corresponds to 2^n Binary numbers （n position ,n by nums length ）. And these binary numbers are continuous , Its decimal size ranges from 0 To 2^n - 1.
We can enumerate decimal values from 0 To 2^n - 1 Binary number of （n position , Front complement 0） To get all the corresponding subsets . For one of the binary numbers , If the first i Position as 1, be nums[i] Join the current subset .
To judge a decimal number m After converting to binary, the i Whether bit is bit 1, We can use it and 2^i Find the position and &. because 2^i Binary number of , Except for i Is it 1 The others are 0, If m Of the i It's also 0, Then the two are bitwise and must be 0, Otherwise 1.

solution 3： to flash back （ Depth-first search ）
Depth first search , Each path corresponds to a different subset , Depth is nums.length. There are taking and not taking on each floor nums[i] Two options , Reach the leaf node （ The first n layer ） Record the subset corresponding to the current path . A lot of backtracking problems have been done before , This problem is simpler , There are only two options on each floor , You can put it first. nums[i] Join in , Then drill down , Go back and take out this number , And search down without taking the number .

Finally, The code with detailed comments is placed in my Personal blog http://jinhuaiyu.com/leetcode-subsets/