Implement Bit Manipulation TricksStep 5 of 5

Enumerate Subsets with Bitmasks

12345

Step 5: Enumerate Subsets with Bitmasks

A list of k items has 2**k subsets, and each subset maps to a k-bit number: bit i set means include nums[i].

Iterate every mask from 0 to 2**k - 1. For each mask, include nums[i] whenever bit i is set. Return the subsets in increasing-mask order.

For [1, 2] the masks 0, 1, 2, 3 give [], [1], [2], [1, 2].

Implement subsets_via_bitmask(nums).

Hints
Starter code
def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count


def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0


def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result


def get_bit(n, i):
    return (n >> i) & 1


def set_bit(n, i):
    return n | (1 << i)


def clear_bit(n, i):
    return n & ~(1 << i)


def toggle_bit(n, i):
    return n ^ (1 << i)


def subsets_via_bitmask(nums):
    """Return all subsets of nums, ordered by increasing bitmask value.

    Mask bit i set means include nums[i]. Iterate masks 0 .. 2**len(nums) - 1.
    """
    # TODO: for each mask in range(1 << len(nums)), build the subset by
    # including nums[i] whenever mask has bit i set; collect all subsets.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges