Today is the 105th day of xiaohao algorithm “365 brush problem plan”. This is yesterday a classmate interview quick hand was asked the algorithm problem, unfortunately he was failed. Share with others after asking for their consent
01. Examples of topics
Subset: Set A is called A subset of set B if any member of set A is A member of set B.
| Problem 48: Subsets |
|---|
| Given a set ofNo repeating elementsInteger array ofnumsReturns all possible subsets (power sets) of this array. |
Note: The solution set cannot contain duplicate subsets
Example:
Input: nums = [1,2,3]
Output: [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]
Copy the codeThe title itself does not need to supplement too much, junior high school mathematics knowledge:
02. Problem Solving Analysis (Advanced)
That was a really cool problem to solve.
First we can prove that there are 2^N subsets of N elements:
You can think of it as N different balls, you pick up a bunch of balls at a time, you can pick up or not pick up any of them, you have N balls, you make N judgments, you have 2 to the N subsets. For example: 123, there are eight subsets:
And then thinking about how to do it, without going back, we can actually use binary to simulate whether each element is selected or not. And since we know that there are 2 to the N subsets for N elements, we just iterate over 2 to the N elements.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
// Store all subsets
List<List<Integer>> res = new ArrayList<>();
// The total number of subsets is 2^N
int length = 1 << nums.length;
// Iterate over all subsets
for (int i = 0; i < length; i++) {
List<Integer> sub = new ArrayList<>();
//TODO: find the corresponding subset element
}
return res;
}
}
Copy the codeBut we don’t know the specific subset elements. So how do we find the subset elements? For 2^N n-bit binary numbers, we can indicate whether we are in the subset set by zeros and ones from the JTH bit back.
for (int j = 0; j < nums.length; j++) {
if (((i >> j) & 1) = =1) sub.add(nums[j]);
}
Copy the codeTo summarize the code:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
// Store all subsets
List<List<Integer>> res = new ArrayList<>();
// The total number of subsets is 2^N
int length = 1 << nums.length;
// Iterate over all subsets
for (int i = 0; i < length; i++) {
List<Integer> sub = new ArrayList<>();
for (int j = 0; j < nums.length; j++) {
if (((i >> j) & 1) = =1) sub.add(nums[j]);
}
res.add(sub);
}
return res;
}
}
Copy the codeTo help you understand, assuming nums is [1,2,3], the stored procedure for res is:
So you can kind of think about this problem.
03. Problem Solving Analysis (General)
Of course, the above solution is not something that ordinary people can think of directly. So here we give a more general solution
The selection/non-selection of all elements in the set constitutes a full binary tree. Left subtree is selected, right subtree is not selected. So, of course, the path from the root node to all the leaves nodes is all the subsets.
So this solution is actually a lot easier to understand:
class Solution {
List<List<Integer>> res;
public List<List<Integer>> subsets(int[] nums) {
res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
dfs(nums, 0, list);
return res;10 }
private void dfs(int[] nums, int start, List<Integer> list) {
for (int i = start; i < nums.length; i++) {
list.add(nums[i]);
dfs(nums, i + 1, list);
list.remove(list.size() - 1);
}
res.add(new ArrayList<>(list));
}
}
Copy the codeIn a word, this topic actually has some difficulties, the main difficulties include:
- The confusion of mathematical knowledge, forget to consider the empty set and so on.
- Confused with the full permutation problem, 2 to the N equals N! To deal with.
- Poor grasp of recursion and backtracking details.
But it is not impossible to conquer, I suggest you go down to practice some ~
Come on, Ollie!
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download
