Subsets and Power Set
Generate all subsets of a set using backtracking and bit-masking, handling duplicates by sorting and skipping repeated elements.
Subsets and Power Set is a free DSA Interview Prep lesson on CoddyKit — 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 DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Subsets and the Power Set
The power set of a set S is the collection of all possible subsets of S, including the empty set and S itself. A set of n elements has exactly 2ⁿ subsets. For [1, 2, 3], the 8 subsets are: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. This is a fundamental combinatorial problem that appears in interview questions about finding all possible combinations, partitions, or choices.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Backtracking Subset Generation
Use the choose-explore-unchoose template. The key design decision: at each recursive call, add the current partial path to results immediately (before choosing more elements). This way, every state — empty, partial, and full — is captured as a valid subset. Advance the start index to only consider elements to the right of the last chosen element, ensuring no duplicates and preserving order.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Bit Masking Approach
An alternative to backtracking is bit masking: each subset corresponds to an n-bit number where bit i being 1 means element i is included. Iterate from 0 to 2ⁿ - 1 and for each number, extract the bits to build the subset. This is iterative, often faster in practice, and very easy to code. However, it doesn't generalise as cleanly to problems with constraints (like sum limit).
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differIterative Subset Generation
The iterative approach builds up the power set element by element. Start with [[] ] (the empty set). For each new element, duplicate all existing subsets and append the new element to each duplicate. After processing n elements, the result contains all 2ⁿ subsets. This is equivalent to bit masking but more readable for those unfamiliar with bitwise operations.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subsets II: Handling Duplicates
When the input contains duplicates, the naive approach generates duplicate subsets. For [1, 2, 2], both occurrences of 2 would produce [1, 2] independently. Fix: sort the array first, then skip a candidate at the current level if it equals the previous candidate at the same level. Specifically, in the loop: if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsWhy the Duplicate Skip Works
The condition i > start and nums[i] == nums[i-1] skips a duplicate only at the same recursion level (same start). It does not prevent selecting the same value at different depths. For [1, 2, 2]: at level 0, we include the first 2 (index 1), then at the next level (start=2), include the second 2 to form [2, 2]. But if we tried to include the second 2 at level 0 again, the condition catches and skips it.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Subsets of Fixed Size (k-Combinations)
Generating only subsets of exactly size k (LeetCode 77: Combinations) adds an early termination condition: if the remaining elements cannot fill the path to size k, prune. The prunable condition is i > n - (k - len(path)): if there aren't enough elements left, stop early. This significantly reduces the search space compared to generating all subsets and filtering.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Power Set Applications
The power set pattern appears in many interview variants: (1) Partition into two equal subsets — check if any subset sums to total/2. (2) Maximum XOR of two subsets — try all subset pairs. (3) Minimum cost to choose k items — enumerate k-subsets. While direct enumeration is exponential, many of these problems admit DP solutions once you recognise the structure. The power set framing helps you identify the state space even when you will optimise it.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Subset Sum Check
Subset Sum asks: does any subset of the array sum to a target? This can be solved by backtracking (exponential) or DP (polynomial). The backtracking version is straightforward but becomes impractical for large inputs. The DP version (boolean table dp[target+1]) is the preferred approach for interviews. Understanding both helps you communicate the trade-off: backtracking gives all solutions, DP answers the decision problem efficiently.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueComplexity of Subset Enumeration
Generating all subsets has unavoidable O(n × 2ⁿ) time complexity — 2ⁿ subsets each of average size n/2. No algorithm can do better when all subsets are requested. For problems asking for a single subset with a property (like maximum sum), DP or greedy should be preferred. Key interview insight: always ask whether you need to enumerate all subsets or just find if any subset satisfies a condition — the answer determines whether exponential or polynomial time is acceptable.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Comparing All Three Approaches
For generating all subsets: Backtracking is the most generalizable — easily adapts to duplicates and constraints. Bit masking is concise and fast but limited to n ≤ 30 (integer size). Iterative is intuitive and avoids recursion overhead. All three produce O(n × 2ⁿ) output. In an interview, backtracking demonstrates understanding of the recursive decision process, which generalises to harder problems. Mention all three when discussing approaches.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: backtracking generates all subsets by adding each partial path to results before exploring further, duplicates are handled by sorting and skipping repeated values at the same recursion depth with the condition i > start and nums[i] == nums[i-1], and bit masking provides a concise iterative alternative where each subset maps to a unique bitmask. Next up we tackle Permutations and Combinations — related enumeration problems with different constraints.
Frequently asked questions
Is the “Subsets and Power Set” lesson free?
Yes — the full text of “Subsets and Power Set” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Subsets and Power Set”?
Generate all subsets of a set using backtracking and bit-masking, handling duplicates by sorting and skipping repeated elements. You practise DSA 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 DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Subsets and Power Set” 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 DSA Interview Prep lesson?
Yes. Every DSA 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.