Let w = {11, 13, 24, 7} and m = 31. Find all possible subsets of w that sum to…

CONCEPT: The sum-of-subsets problem is solved by backtracking on a fixed-tuple-size state space tree: level i of that tree decides one bit xi, where xi = 1 puts the weight wi into the subset and xi = 0 leaves it out, so every root-to-leaf path is one candidate vector (x1, x2, ..., xn). A node whose chosen weights already add up to s, with r = wi+1 + ... + wn still undecided, is promising — worth expanding — only while both bounds hold: s + r ≥ m, so enough weight is still available to reach the target, and s + wi+1 ≤ m, so the next weight still fits. A node that fails either bound is non-promising and its whole subtree is never explored, which is why only a portion of the complete 2n-leaf tree is generated. The second bound is valid only when the weights are arranged in non-decreasing order, so the list is sorted before the search starts.

APPLICATION: Here w = {11, 13, 24, 7}, n = 4 and m = 31. Sorting the weights into non-decreasing order gives (w1, w2, w3, w4) = (7, 11, 13, 24) with total weight 7 + 11 + 13 + 24 = 55. The search starts at the root with s = 0 and r = 55; at every node the left branch takes the current weight and the right branch skips it.

1. Root, s = 0, r = 55: 0 + 55 = 55 ≥ 31 and 0 + 7 = 7 ≤ 31, so the root is promising and both of its children are generated.

2. Take 7, giving s = 7 and r = 48: 7 + 48 = 55 ≥ 31 and 7 + 11 = 18 ≤ 31, so this node is expanded.

3. Take 7 and 11, giving s = 18 and r = 37: 18 + 37 = 55 ≥ 31 and 18 + 13 = 31 ≤ 31, so this node is expanded.

4. Take 7, 11 and 13, giving s = 31: the chosen weights already equal m = 31, so this is an answer node and the branch stops here; it yields the subset {7, 11, 13}.

5. Take 7 and 11 but skip 13, giving s = 18 and r = 24: enough weight remains, since 18 + 24 = 42 ≥ 31, but the only weight left does not fit, since 18 + 24 = 42 > 31, so this node is cut off.

6. Take 7 but skip 11, giving s = 7 and r = 37: 7 + 37 = 44 ≥ 31 and 7 + 13 = 20 ≤ 31, so this node is expanded.

7. Take 7, skip 11 and take 13, giving s = 20 and r = 24: 20 + 24 = 44 ≥ 31, but 20 + 24 = 44 > 31, so the last weight cannot be added and this node is cut off.

8. Take 7 but skip both 11 and 13, giving s = 7 and r = 24: 7 + 24 = 31 ≥ 31 and 7 + 24 = 31 ≤ 31, so both bounds are exactly tight and this node is expanded.

9. Take 7, skip 11 and 13, then take 24, giving s = 31: this is the second answer node and it yields the subset {7, 24}. Its sibling, which skips 24 as well, has s = 7 and r = 0, so 7 + 0 = 7 < 31 and that sibling is cut off.

10. Skip 7, giving s = 0 and r = 48: 0 + 48 = 48 ≥ 31 and 0 + 11 = 11 ≤ 31, so this node is expanded.

11. Skip 7 and take 11, giving s = 11 and r = 37: 11 + 37 = 48 ≥ 31 and 11 + 13 = 24 ≤ 31, so it is expanded, but both of its children fail the fit bound — taking 13 gives 24 + 24 = 48 > 31, and skipping 13 gives 11 + 24 = 35 > 31 — so both are cut off.

12. Skip both 7 and 11, giving s = 0 and r = 37: 0 + 37 = 37 ≥ 31 and 0 + 13 = 13 ≤ 31, so it is expanded, and again both children fail — taking 13 gives 13 + 24 = 37 > 31, and skipping 13 leaves only 24 of weight, so 0 + 24 = 24 < 31.

Collecting those nodes gives the generated portion of the state space tree. Each row below is one generated node, identified by the weights taken along its path, its included sum s and the weight r still undecided.

CROSS-CHECK: Testing all 24 = 16 subsets confirms the result. The empty subset gives 0; the four singletons give 11, 13, 24 and 7; the six pairs give 24, 35, 18, 37, 20 and 31; the four triples give 48, 31, 42 and 44; and the whole set gives 55. Exactly one pair, {24, 7}, and exactly one triple, {11, 13, 7}, reach 31, so the two bounds discarded no solution.

RESULT: Exactly two subsets of w sum to 31, namely {11, 13, 7} and {24, 7}. Written as fixed-size vectors over the weights in the order given in the question, (11, 13, 24, 7), they are (1, 1, 0, 1) and (0, 0, 1, 1). The generated portion of the tree holds 17 of the 31 nodes of the complete four-level tree: 10 promising nodes, including the two answer nodes, and 7 nodes cut off by the bounds.