Backtracking Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the whole module: choose the right pattern from the question, write the template, handle duplicates and prune with a rule. Decide first what an answer looks like and how many answers there can be, then write the search.
Pick the pattern from the question
Answer count is how many results a search can produce: 2 to the n for subsets, n choose k for combinations and n factorial for permutations. It is the least time the search can take.
Read the question before writing code. Each item in or out is a subset. A group of k where order is ignored is a combination. Every item once in some order is a permutation.
from itertools import combinations, permutationsfrom math import comb, factorial
print(2 ** 4, comb(4, 2), factorial(4))print(len(list(combinations(range(4), 2))), len(list(permutations(range(4)))))Example 1 · Answer counts for five items
from itertools import combinations, permutationsfrom math import comb, factorial
items = range(5)print(2 ** 5, comb(5, 2), factorial(5))print(sum(1 for _ in combinations(items, 2)), sum(1 for _ in permutations(items)))32 10 120 10 120
What this code does
- A search that lists every permutation of 5 items does 120 units of work before copying anything.
- Check the answer count first. If it is in the millions, the search needs pruning or a different method.
The formulas and the built-in generators agree: 16 subsets, 6 pairs and 24 orders for 4 items.
One template, many problems
Every solution has the same frame: a path, a base case that saves a copy, a loop over the choices and an undo. Only the list of choices and the rule that accepts one change.
def search(choices, is_ok, size): result = [] def walk(path): if len(path) == size: result.append(path[:]) return for item in choices: if is_ok(path, item): path.append(item) walk(path) path.pop() walk([]) return resultprint(len(search("abc", lambda p, x: x not in p, 3)))Example 2 · One template with three rules
def search(choices, is_ok, size): result = [] def walk(path): if len(path) == size: result.append(path[:]) return for item in choices: if is_ok(path, item): path.append(item) walk(path) path.pop() walk([]) return result
print(len(search("abc", lambda p, x: True, 2)))print(len(search("abc", lambda p, x: x not in p, 3)))print(len(search("abc", lambda p, x: not p or p[-1] != x, 3)))9 6 12
What this code does
- Accepting every letter gives 3 x 3 = 9 words of length 2.
- Rejecting a letter already in the path gives the 6 permutations.
- Rejecting a letter equal to the last one gives 3 x 2 x 2 = 12 words.
The rule x not in p turns the search into permutations of three letters, so six words are made.
Duplicates and early stops
Sort and skip an equal neighbour at the same level when the input has repeats. Pass path + [x] and no undo is needed, because every call gets its own new list.
def combos(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 if i > start and nums[i] == nums[i - 1]: continue walk(i + 1, path + [nums[i]], left - nums[i]) walk(0, [], target) return resultExample 3 · Unique combinations that reach a target
def combos(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 if i > start and nums[i] == nums[i - 1]: continue walk(i + 1, path + [nums[i]], left - nums[i]) walk(0, [], target) return result
print(combos([3, 1, 2, 2, 4, 6], 6))[[1, 2, 3], [2, 4], [6]]
What this code does
- Sorting gives 1, 2, 2, 3, 4, 6, so the equal 2s are neighbours.
- [2, 4] is listed once, even though two different 2s could be used.
- Each answer list is new, so no undo is needed.
The break prunes numbers that are too big and the continue skips repeats. Return a list for all answers, a boolean for one answer, or a number for a count.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
For 5 items print on one line the number of subsets, the number of pairs and the number of orderings, separated by spaces.
32 10 120
Exercise 2· Easy
Use itertools.combinations to print every pair from ["Asha", "Ravi", "Meena"] on its own line, names separated by a space.
Asha Ravi Asha Meena Ravi Meena
Exercise 3· Medium
Count the subsets of [2, 3, 5] whose items add up to at least 5. Print the count.
5
Exercise 4· Medium
Three shifts Day, Eve and Night are assigned in some order, but Night may never be first. Use a search with a rule and print how many orders are allowed, then the first one as a list.
4 ['Day', 'Eve', 'Night']
Exercise 5· Medium
Print all different subsets of [1, 1, 2] as a list of lists. Sort first and skip repeats at the same level.
[[], [1], [1, 1], [1, 1, 2], [1, 2], [2]]
Exercise 6· Hard
Choose 3 different numbers from 1 to 9 that add up to 15. Print how many groups exist and then the first group and the last group (numbers in increasing order within a group, groups built in order).
8 [1, 5, 9] [4, 5, 6]
Exercise 7· Hard
Find the first placement of 6 queens on a 6 by 6 board (rows top to bottom, columns tried left to right) and print the column of the queen in each row as a list.
[1, 3, 5, 0, 2, 4]
Exercise 8· Hard
Tasks take [3, 1, 4, 2, 2, 2] minutes. Find the first subset (taking items from left to right, trying to take an item before skipping it) that adds up to exactly 7 minutes and print it as a list. Stop searching once you have it.
[3, 4]
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Backtracking