How to use Bit full search

Bit full search is a method to do full search by using bit operation.
This method are used when we solve subset problems.
Subset is a set of whose elements are all members of another set. For example, if we have a set A = {1, 2, 3}, then some subsets of A would be {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}

if you don't know about bit, I recommend you to read this article.

To explain bit full search, I reference Subsets by LeetCode.

Answer

At first, I show the answer code.

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let n = nums.len();
        for bit in 0..(1 << n) {
            let mut vec = Vec::new();
            for i in 0..nums.len() {
                if bit & (1 << i) != 0 {
                    vec.push(nums[i]);
                }
            }
            res.push(vec);
        }
        res
    }
}

Let's dive into

for bit in 0..(1 << n) {
  // TODO:
}

for n in 0..(1 << n) { show 2^n
meaning it represents 2 raised to the power of n.
That is, 2 raised to the nth power.
we can iterate the loop as many times as the number of subsets

Why the loop count of subsets is 2 raised to the power of n?

Given a set of '[a, b, c]', there are two possibilities of including or excluding a, two possibilities of including or excluding b, and possibilities of including or excluding c. so it will be 2 to the 3rd power.

&(AND)

if bit & (1 << i) != 0 {
    vec.push(nums[i]);
}

Here I use &.
& means that Compares two bits and returns 1 if both are 1 and 0 if either is 0.
Therefore, if 1 is returned, all patterns can be showed by putting i in the array.

Summarize

We can solve subset problems by using bit specifications.
You may find it challenging to fully understand the concept by just listening to an explanation. However, writing the code by yourself can provide a deeper understanding.