Leetcode -78 bit operation solution

The original link

Leetcode-cn.com/problems/su…

Topic describes

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

• Example 1:

Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the code

• Example 2:

Nums = [0] Output: [[],[0]]Copy the code

solution

For example, nums = [1, 2, 3]

First, paste a table of the official solution, which consists of the binary numbers corresponding to the 0/1 sequence, the subset, and the 0/1 sequence

So you can see, if we use 1 for this digit, and 0 for not taking this digit, we get all 8 of these results

• So here’s the first problem, one of lengthnHow many results are there?

The answer is 2 to the n, because an n-length array has n positions, all covered up, 11… 1 n ones, if you convert it to binary, 2 to the n minus 1, plus 0, 2 to the n

And 2 to the n, in binary terms, is 1 << n

So, let’s write the first piece of code

var subset = function (nums) { const n = nums.length; for (let i = 0; i < (1 << n); i++) { // do something... }}Copy the code

Thus, we can loop through all the 0/1 sequences from 000 to 111 (nums = [1, 2, 3] for example) and create a temporary array TMP

var subset = function (nums) { const n = nums.length; const ret = []; for (let i = 0; i < (1 << n); i++) { const tmp = []; for (let j = 0; j < n; j++) { if ( // do something... ) { tmp.push( // valid number ); } } ret.push(tmp); }}Copy the code

Loop through the numS to see if the current nums exists in the current 0/1 sequence. If so, put the current nums into TMP. After loop nums, put TMP into the returned array RET

• So the second question is, how do you tell if this current number exists in the current 0/1 sequence?

For example, there is a sequence of 0/1:101, which represents a subset of {1, 3}. When we loop to 1 and 3, how can we determine that it exists in the sequence of 0/1:101?

In fact, we can determine which index of the 0/1 sequence is 1, because the index of the 0/1 sequence corresponds to the index of nums

For example, for the number 1, we determine whether the first digit of 101 is a 1

So let’s move 101 two places to the right 101 >> 2 to find his first digit

The first digit is then ampersand with 1. If it is 1, it is 1; otherwise, it is 0

If (I >> j) &1 === 1(I >> j) &1 === 1(I >> j) &1 === 1(I >> j) &1 === 1(I >> j)

To add:

var subset = function (nums) {
    const n = nums.length;
    const ret = [];
    for (let i = 0; i < (1 << n); i++) {
        const tmp = [];
        for (let j = 0; j < n; j++) {
            if ((i >> j) & 1 === 1) {
                tmp.push(nums[j]);
            }
        }
        ret.push(tmp);
    }
    return ret;
}
Copy the code

conclusion

I didn’t quite understand the official solution of Leetcode, and I did a lot of searching before I understood the meaning of a bunch of bit operations in the code. I hope to write this article to help you