Last week I wrote about solving UVa 11085 using the recursive backtracking search technique. This week, I’m going to outline a more general approach to recursive backtracking problems. Then I’ll show how it can be adapted to solve UVa 574.

UVa 574 asks us to solve this problem:

Given a multiset $S$ of integers and a target sum $t$, find all subsets of $S$ that sum to $t$.