Contest Python: USACO Bronze › Unit 9 — Recursion & Backtracking
Exercises: Unit 9 — Recursion & Backtracking
Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, then print. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Target Subset Count
The first line contains N T, and the second line contains N distinct positive integers; use recursive backtracking to include or skip every value and print the number of subsets whose sum is exactly T, counting the empty subset when T is 0. In the sample, a branch that includes 7 must recurse, come back, and undo before the search can find other answers, and the final value 3 completes two of the three valid subsets.
Constraints. 0 <= N <= 20 and 0 <= T <= 200.
Every value is distinct and between 1 and 50.
Your named recursive search must make both the include and skip choice for each value.
Sample Input
5 10
2 4 7 1 3Sample Output
3How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 2: Spaced Permutation Count
The first line contains N K, and the second line contains N distinct integers; recursively build every permutation and print how many have an absolute difference of at least K between every pair of neighboring values. A rejected neighbor must be undone so another unused value can be tried, and the final input value is part of valid sample orderings.
Constraints. 1 <= N <= 9 and 0 <= K <= 20.
Every value is distinct and between 0 and 30.
Use backtracking over unused values; permutation-library shortcuts are not allowed.
Sample Input
4 2
1 2 3 5Sample Output
4How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 3: Queens Without Conflict
The input contains one integer N; place one queen in every row of an N by N board and print the number of placements in which no two queens share a column or diagonal. Recurse row by row, undo each attempted column and diagonal before trying the next column, and count a placement only when the base case reaches row N.
Constraints. 1 <= N <= 10.
Rows and columns are zero-indexed while searching.
Do not build a graph or tree; track only the partial placement and its occupied columns and diagonals.
Sample Input
4Sample Output
2How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 4: Coin Bag Combinations
The first line contains N T, and the second line contains N distinct positive coin values in increasing order; you may use each value any number of times, and you must print the number of different combinations that total T, where order does not create a new combination. Recursively try a count for one coin value, recurse, come back, and undo that partial total, then try the next count; in the sample, the three coin values combine into the four totals {5,5}, {5,3,2}, {3,3,2,2}, and {2,2,2,2,2}.
Constraints. 1 <= N <= 8 and 0 <= T <= 50.
1 <= coin value <= 50, and the values are distinct and increasing.
The recursion must advance through coin indices so reordered copies of one combination are counted once.
Sample Input
3 10
2 3 5Sample Output
4How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 5: Nested Expression Score
The input is one expression string with no spaces; every expression is either a nonnegative integer or exactly (left+right), (left-right), or (left*right), where left and right are expressions. Recursively evaluate the flat string and print its integer value: a number is the base case, and for a parenthesized expression you must find the operator belonging to the outer pair, recursively evaluate both substrings, and combine them. The sample's final nested 2 changes the result, so parsing only the earlier part is incorrect.
Constraints. The expression has at most 200 characters and nesting depth at most 30.
Every integer is between 0 and 999, and division does not appear.
Parse the expression string directly; do not create node objects or a tree structure.
Sample Input
((12+3)*(4+(5*2)))Sample Output
210How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 6: Fractal Trail Count
A self-similar trail starts at level 0 with one empty route; at every later level, each partial route grows three branches labeled 0, 1, and 2. The input contains N T; recursively choose one branch label at each of the N levels and print the number of complete routes whose labels sum to T. After exploring one label, undo it before trying the next, and count a route only at the depth-N base case; the last label choice 2 is necessary for some sample routes.
Constraints. 0 <= N <= 12 and 0 <= T <= 24.
Every level has exactly the three labels 0, 1, and 2.
Use a named recursive backtracking function rather than a closed formula.
Sample Input
4 6Sample Output
10How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 7: Equal Team Partitions
The first line contains N, and the second line contains N positive skill values; split every player into team A or team B and print the number of equal-total partitions, treating swapped team names as the same partition. To avoid counting a swap twice, player 0 must always be placed on team A; recursively choose a team for every later player, undo before the other choice, and compare totals only at the base case. The final player's value is required for the sample's equal split.
Constraints. 1 <= N <= 20.
Every skill value is between 1 and 30.
Player 0 is fixed on team A, and every other player must be assigned exactly once.
Sample Input
4
2 1 4 3Sample Output
1How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 8: Smallest Spaced Permutation
The first line contains N K, and the second line contains N distinct digits; recursively build permutations and print the lexicographically smallest digit string whose neighboring digits differ by at least K, or print NONE if no such ordering exists. Try remaining digits in increasing order and undo every rejected choice; because the search explores smaller digits first, the first complete valid permutation it finds is automatically the lexicographically smallest. In the sample, the smallest ordering of 1 2 3 5 whose neighboring digits differ by at least 2 is 1352.
Constraints. 1 <= N <= 9 and 0 <= K <= 9.
Each digit is between 0 and 9, and all digits are distinct.
Build the one output string with + concatenation; permutation-library shortcuts are not allowed.
Sample Input
4 2
1 2 3 5Sample Output
1352How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 9: Queens With Blocked Squares
The first line contains N B, and each of the next B lines contains a zero-indexed blocked square row column; place one queen in every row and print the number of placements in which no queen uses a blocked square and no two queens share a column or diagonal. Recurse row by row, undo every attempted column and diagonal before the next attempt, and count only at the row-N base case; the final blocked square in the sample lies in the last row and changes the answer.
Constraints. 1 <= N <= 10 and 0 <= B <= N * N.
Every blocked square is distinct, with 0 <= row < N and 0 <= column < N.
Do not build a graph or tree; use backtracking over rows and occupied columns and diagonals.
Sample Input
5 2
0 0
4 4Sample Output
6How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.