Coding Grandmaster · project 17 of 46 · premium, free for now

Every subset

Write subsets(items) returning a list of every subset as a list, in the order of the counter 0 to 2^n − 1, using bit tests. Print how many subsets four items have, and the subsets of two items.

Learn

A list of n items has 2^n subsets: each item is either in or out. Count from 0 to 2^n − 1 in binary; bit i of the counter says whether item i is in the subset. So a single loop and a bit test generate the lot. This power set idea sits behind many puzzles and search problems.

Your task

Write subsets(items) returning a list of every subset as a list, in the order of the counter 0 to 2^n − 1, using bit tests. Print how many subsets four items have, and the subsets of two items.

Stretch challenge

Find the subsets of [3, 5, 8, 13] that add up to 16.

← Set, clear and toggle Permission flags →

Python

Press Run to see what your program prints.

Keep going in Coding Grandmaster

Seeing the bits

Print each of 5, 12 and 255 as 8 binary digits, and write count_ones(n) that counts the 1 bits using & and >>.

Start →14

One-line bit tricks

Write is_power_of_two(n) using n & (n - 1), is_odd(n) using n & 1, and print the powers of two up to 200 using a list comprehension.

Start →15

XOR magic

Swap a and b with three XOR lines (no temporary variable), and write lonely(numbers) that returns the number that appears only once by XOR-ing everything together.

Start →16

Set, clear and toggle

Write set_bit(n, i), clear_bit(n, i), toggle_bit(n, i) and test_bit(n, i) (True or False) using shifts and bitwise operators.

Start →18

Permission flags

With READ = 4, WRITE = 2 and EXEC = 1, write grant(perms, flag), revoke(perms, flag), has(perms, flag) and describe(perms) which returns text like r-x (r, w and x, or - for a missing one).

Start →

Practise the idea

🃏 Play Maths Memory Match

Flip cards to match each sum with its answer. Times tables, addition, fractions and percentages.

Play now

FAQ

Every subset: common questions

I am stuck. What can I do?

Press Hint for a nudge, read the message next to each goal, and compare your code with the lesson text. If you still need it, Show answer reveals a model solution. Try to type it yourself rather than copy it.

Does my work get saved?

Your ticks and XP are saved in this browser, and in your account if you log in. The code you type is not stored on a server.

Start a conversation

Enjoying coding? Meet a teacher.

Tell us the learner's age, country and what they would like to build, and we will suggest a class. A parent or guardian can make the enquiry.

Tell us the learner’s age or grade and goals
We’ll suggest a suitable class or learning path
We’ll confirm format, timing and fees with a parent or guardian

Play it, don't just read it

Write some code right now

Free games that need no sign-up. Pick one and play for five minutes.

All free games →

Pick a game

Today's maths challengeFive questions · the same for everyone today · keep your streak goingPlay