Subsets Generation Using Bitmask in DSA Python - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of fruits and you want to see all possible groups you can make from them. This is like choosing different combinations of fruits to pack in a basket.

🎯 Goal: You will write a program that takes a list of fruits and generates all possible subsets (groups) of these fruits using a bitmask technique.

📋 What You'll Learn

Create a list called fruits with the exact values: 'apple', 'banana', 'cherry'

Create a variable called n that stores the length of the fruits list

Use a for loop with variable bitmask to go from 0 to 2**n - 1

Inside the loop, create a list called subset that holds fruits selected by the current bitmask

Print each subset on a new line

💡 Why This Matters

🌍 Real World

Generating subsets is useful in situations like choosing different combinations of items, planning menus, or exploring options in decision making.

💼 Career

Understanding subsets and bitmasking helps in coding interviews, optimization problems, and tasks involving combinations in software development.

1

Create the list of fruits

Create a list called fruits with these exact values: 'apple', 'banana', 'cherry'

DSA Python

# Create the list of fruits
# Your code here

Hint

Use square brackets [] to create a list and separate items with commas.

2

Calculate the number of fruits

Create a variable called n that stores the length of the fruits list using the len() function

DSA Python

fruits = ['apple', 'banana', 'cherry']
# Create variable n to store length of fruits
# Your code here

Hint

Use len(fruits) to get the number of items in the list.

3

Generate subsets using bitmask

Use a for loop with variable bitmask to go from 0 to 2**n - 1. Inside the loop, create a list called subset that holds fruits where the bit at position i in bitmask is set. Use another for loop with variable i from 0 to n-1 to check each bit.

DSA Python

fruits = ['apple', 'banana', 'cherry']
n = len(fruits)
# Use a for loop with bitmask from 0 to 2**n - 1
# Inside, create subset list using bits
# Your code here

Hint

Use bitmask & (1 << i) to check if the ith bit is set in bitmask.

4

Print each subset

Add a print(subset) statement inside the for bitmask loop to display each subset on a new line

DSA Python

fruits = ['apple', 'banana', 'cherry']
n = len(fruits)
for bitmask in range(2 ** n):
    subset = []
    for i in range(n):
        if bitmask & (1 << i):
            subset.append(fruits[i])
    # Print the subset
    # Your code here

Hint

Use print(subset) to show each group of fruits.