Leetcode 78. Subsets

78. Subsets

Solutions

Regular simulating the whole process

power set is like the binary number, for each number we have two options:

put it into the set or not put it into the set.

say we have nums = {a,b,c,d}

• for a: not put: {}, put: {a} -> {}, {a}
• for b: not put: {}, {a}, put: {b}, {a,b} ->{},{a},{b}, {a,b}
• for c: not put:{},{a},{b}, {a,b}, put: {c}, {a,c}, {b,c}, {a,b,c} ->{},{a},{b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}
• for c: not put {},{a},{b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}, put:{d},{a,d},{b,d}, {a,b,d}, {c,d}, {a,c,d}, {b,c,d}, {a,b,c,d}
• Done, we get the result of {},{a},{b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}, {d},{a,d},{b,d}, {a,b,d}, {c,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

You get the whole process, right?

Code is simple.’

python code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for n in nums:
            res += [[n]+r for r in res]
        return res

C++ code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int>> ret;
        ret.push_back(vector<int>{});
        for (auto num:nums)
        {   
            auto L = ret.size();
            for (int i=0;i<L;++i)
            {
                auto this_s = ret[i];
                this_s.push_back(num);
                ret.push_back(this_s);
            }
        }
        return ret;
    }
};

Bit manipulation

we know that a power set has the elements of 2^n. We also know that b bits binary number will contain 2^n different numbers. Such as 2 bits we will have 00, 01, 10, 11.

We can exactly use the binary number to represent whether one element is in the set or not.

for example, if we have [a,b]

• 00: []
• 01:[b]
• 10:[a]
• 11: [ab]

the code will be

supposed we have a nums

for binary_number from 0 to 2^n-1

for each bit position i, if this bit is 1, add nums[i] into the set.

How to decide whether a bit position is one?

we can use bit manipulation

in this demonstration, I am using the reverse index, which means that the index is from n-1 to 0. You can also try to use a regular index which is from 0 to n-1.

for example, if we have nums=[a,b,c,d]

for 0101

• 0101 & (1<<0) = 0101&1 = 1: add d in to the result {d}
• 0101 & (1<<1) = (0101&10) = 0: do not add c
• 0101 &(1<<2) = (0101&100) = 100: add b to the result, we will get {b,d}
• 0101 &(1<< 3) = (0101&1000) = 0: do not add ‘a’ to the result. Done. we get {b,d}

python code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        size = 1<<len(nums)
        res = []
        for i in range(size):
            this_res = []
            for j,n in enumerate(nums):
                if (1<<j)&i:this_res.append(n)
            res.append(this_res)
        return res

c++ code is here:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int>> ret;
        const int n = nums.size();
        for(int j=0;j<(1<<n);++j)
        {
            vector<int> this_ret;
            for (int i=0;i<n;++i)
            {
                if(j&(1<<i))
                {
                    this_ret.push_back(nums[i]);
                }
            }
            ret.push_back(this_ret);
        }
        return ret;
    }
};

Thanks for reading.