Generate All Subsets
Choose or skip each element.
Generate All Subsets is a free Coding Interview Prep lesson on CoddyKit. This is lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
Why Generate Subsets
Many contest tasks ask you to try every subset of a small set. With recursion you can list all of them cleanly and reliably. 🧩
Choose or Skip Each Element
The core idea: for each element you make one binary choice, include it or leave it out. Every full set of choices gives one subset.
How Many Subsets Exist
A set of n elements has exactly 2 to the n subsets, because each element doubles the count. So keep n small, around 20 or less.
The Recursive Plan
Walk an index through the array. At each index, branch twice: once taking the element, once skipping it.
The Base Case
When the index passes the last element, the current path is one complete subset. That moment is your base case to record it.
Subset Recursion in Code
This recursive sweep records a subset at the end, then explores skip and take from each index.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Backtrack by Undoing
When you append an element, remove it after recursing so the next branch starts clean. That undo step is the heart of backtracking.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()The Bitmask Alternative
You can also map each integer from 0 to 2 to the n minus 1 to a subset, where each bit marks an included element.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Copy Before You Store
Always store a copy of the current list, not the list itself. Otherwise later changes overwrite every subset you saved. ⚠️
Generating Combinations
To get subsets of a fixed size k, stop the branch once the chosen count reaches k. That turns subsets into combinations.
Where Subsets Show Up
Subset enumeration solves small knapsack, team-picking, and feasibility checks where you must test every possible selection.
Quick Check
How many subsets does a set of n elements have?
Recap: Branch on Every Element
You learned to list all subsets by choosing or skipping each element, undoing after each branch. Keep n small since the count is 2 to the n. 🎯
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Generate All Subsets” lesson free?
Yes — the full text of “Generate All Subsets” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Generate All Subsets”?
Choose or skip each element. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.
How long does the “Generate All Subsets” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Think Recursively: Base & Recurse
- Generate All Subsets
- Permutations and the N-Queens Idea
- Prune to Survive the Time Limit