Subsets and Combinations
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems ask for a selection: which tools to install, which players to pick, which prices add up to a budget. These are subsets and combinations. The start index and the take-or-skip choice give you a short pattern for all of them.
Subsets: take it or leave it
Subset is a selection of zero or more items from a list, where each item is either in or out. A list of n items has 2 to the power n subsets, including the empty one.
A team lead picks tools for a project from a short list. Each tool is either in or out. At each item the code takes it or skips it, then moves to the next item.
def subsets(items): result = []
def walk(i, path): if i == len(items): result.append(path[:]) return path.append(items[i]) # take walk(i + 1, path) path.pop() # undo walk(i + 1, path) # skip
walk(0, []) return resultExample 1 · Subsets of three tools
def subsets(items): result = []
def walk(i, path): if i == len(items): result.append(path[:]) return path.append(items[i]) # take walk(i + 1, path) path.pop() # undo walk(i + 1, path) # skip
walk(0, []) return result
print(subsets(["lint", "tests", "docs"]))[['lint', 'tests', 'docs'], ['lint', 'tests'], ['lint', 'docs'], ['lint'], ['tests', 'docs'], ['tests'], ['docs'], []]
What this code does
- Taking an item comes before skipping it, so the first answer holds all three tools and the last is empty.
- Eight subsets appear for three items, as 2 x 2 x 2 predicts.
i is the level. Each level has two branches, so there are 2 to the n leaves, and every leaf is one subset.
A start index: every path is an answer
Start index is the position from which a call may still choose items. Passing i + 1 to the next call keeps the original order, so each group is built only once.
A second style uses a loop. From position start, choose any later item, then continue after it. Every path is already a valid subset, so save it at the top of each call.
def subsets(items): result = []
def walk(start, path): result.append(path[:]) for i in range(start, len(items)): path.append(items[i]) walk(i + 1, path) path.pop()
walk(0, []) return resultExample 2 · Loop version: same subsets, new order
def subsets(items): result = []
def walk(start, path): result.append(path[:]) for i in range(start, len(items)): path.append(items[i]) walk(i + 1, path) path.pop()
walk(0, []) return result
print(subsets([1, 2, 3]))[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
What this code does
- The path is saved when a call starts, so the empty list comes first.
- The order differs from the take-or-skip version, but the eight subsets are the same.
Example 3 · Brute force: all subsets, then filter
def subsets(items): result = []
def walk(start, path): result.append(path[:]) for i in range(start, len(items)): path.append(items[i]) walk(i + 1, path) path.pop()
walk(0, []) return result
prices = [30, 20, 50, 10]within = [s for s in subsets(prices) if sum(s) <= 60]print(len(within))print(max(within, key=sum))10 [30, 20, 10]
What this code does
- Build every subset and keep the ones within the budget of 60.
- This is easy to write and always right, but it builds all 2 to the n subsets even when most are too expensive.
maxwithkey=sumpicks the basket with the highest total.
Passing i + 1 means an item is never used twice, and going only forward means [1, 2] and [2, 1] are not both made.
Combinations of size k
Combination is a group chosen from a set where the order does not matter. Choosing k items from n gives n choose k groups.
A coach picks 2 players from 4. The order does not matter, so (1, 2) and (2, 1) are the same team. Use the start index and save the path when it reaches size k.
def combine(n, k): result = []
def walk(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) walk(i + 1, path) path.pop()
walk(1, []) return resultExample 4 · Combinations of 2 from 4
def combine(n, k): result = []
def walk(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) walk(i + 1, path) path.pop()
walk(1, []) return result
print(combine(4, 2))[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
What this code does
- The start index keeps every team in increasing order.
- Six teams appear, which is 4 x 3 / 2.
Example 5 · Better: stop when too few items are left
calls = [0, 0]
def combine(n, k, tight): def walk(start, path): calls[tight] += 1 if len(path) == k: return last = n - (k - len(path)) + 1 if tight else n for i in range(start, last + 1): path.append(i) walk(i + 1, path) path.pop()
walk(1, [])
combine(10, 8, 0)combine(10, 8, 1)print("plain calls:", calls[0])print("tight calls:", calls[1])plain calls: 1013 tight calls: 165
What this code does
- With
tighton, the loop stops at the last item that still leaves room for the rest of the group. - The answers are the same, but far fewer calls are wasted on paths that can never reach size k. Here the count drops from 1013 to 165.
- Cutting a branch early like this is called pruning.
There are 6 teams from 4 players. Each team is listed in increasing order, so none appears twice.
Sum to a target, reusing numbers
Pick numbers that add up to a target, and any number may be used again. Sort first. When a number is larger than what is left, stop the loop, because every later number is larger too.
def combo_sum(nums, target): nums = sorted(nums) result = [] def walk(start, path, left): if left == 0: result.append(path[:]) return for i in range(start, len(nums)): if nums[i] > left: break # prune path.append(nums[i]) walk(i, path, left - nums[i]) path.pop() walk(0, [], target) return resultExample 6 · Combination sum with reuse
def combo_sum(nums, target): nums = sorted(nums) result = []
def walk(start, path, left): if left == 0: result.append(path[:]) return for i in range(start, len(nums)): if nums[i] > left: break # prune path.append(nums[i]) walk(i, path, left - nums[i]) path.pop()
walk(0, [], target) return result
print(combo_sum([2, 3, 6, 7], 7))print(combo_sum([5, 3], 1))[[2, 2, 3], [7]] []
What this code does
- 2 + 2 + 3 and 7 both reach the target, and each group is listed once.
- When no group works the result is an empty list, not an error.
walk(i, ...) passes i, not i + 1, so the same number can be chosen again. The break cuts every branch that would overshoot.
When itertools is enough
itertools.combinations makes groups of size k and combinations_with_replacement allows reuse. Use them for plain selection. Write your own when you need a running total, an early stop or a rule.
from itertools import combinations
items = [1, 2, 3, 4]print(list(combinations(items, 2)))print(sum(1 for _ in combinations(range(20), 3)))Example 7 · itertools gives the same groups
from itertools import combinations, combinations_with_replacement
def combine(n, k): result = []
def walk(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) walk(i + 1, path) path.pop()
walk(1, []) return result
mine = combine(5, 3)built_in = [list(c) for c in combinations(range(1, 6), 3)]print(mine == built_in)print(len(list(combinations_with_replacement("ab", 3))))True 4
What this code does
combinationsreturns tuples, so each one is turned into a list before comparing.combinations_with_replacementlets an item repeat, which gives aaa, aab, abb and bbb.- In a real project the built-in is the better choice; in an interview you write the recursion.
Both give tuples in input order. Counting with sum(1 for ...) never builds the whole list.
Next step
Check your understanding
12 quick questions