Teaching Kids Programming – Finding All Subsets by Bitmasking Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

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]]

Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Finding All Subsets by Bitmasking Algorithm

Given N unique numbers, the total number of subsets is . Thus, w can iterate the number from 0 to and each number (in binary) corresponds to a selection of numbers in the current subset. For example:

0 – 000 – []
1 – 001 – [1]
2 – 010 – [2]
3 – 011 – [1, 2]
4 – 100 – [3]
5 – 101 – [1, 3]
6 – 110 – [2, 3]
7 – 111 – [1, 1, 1]

For each binary number, we have to loop over each number/index to see if that bit is set – if yes include it in the current subset.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def subsets(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = []        
        for i in range(1 << n):
            cur = []
            for j in range(n):
                if i & (1 << j):
                    cur.append(nums[j])
            ans.append(cur)
        return ans   

class Solution:
    def subsets(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = []        
        for i in range(1 << n):
            cur = []
            for j in range(n):
                if i & (1 << j):
                    cur.append(nums[j])
            ans.append(cur)
        return ans   

The time complexity is O(N*2^N)

Subsets Algorithms

• Teaching Kids Programming – Finding All Subsets by Bitmasking Algorithm
• Teaching Kids Programming – Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)
• Generate the Power SubSet using Depth First Search Algorithm
• Teaching Kids Programming – Cascading Algorithm to Find All Subsets

–EOF (The Ultimate Computing & Technology Blog) —