Find a subset that sums right

The simplest NP-complete arithmetic problem. Shows up in finance, scheduling, and resource allocation.

1. 01
   Same DP shape as knapsack — a Boolean reachability table indexed by sum. For a financial-netting problem with trades up to a million dollars, this is microseconds. When the target gets cryptographically large, switch to meet-in-the-middle or ILP.

   fn subset_sums_to(items: &[u32], target: u32) -> bool {
       let t = target as usize;
       let mut reachable = vec![false; t + 1];
       reachable[0] = true;
       for &v in items {
           let v = v as usize;
           if v > t { continue; }
           for s in (v..=t).rev() {
               if reachable[s - v] { reachable[s] = true; }
           }
       }
       reachable[t]
   }

2. 02
   continue; jumps to the next iteration of the enclosing loop, skipping the rest of the current iteration's body. It is the partner of break;, which exits the loop entirely. On page 30 the line if v > t { continue; } says "if this item is already bigger than the target, no subset including it can possibly hit t, so skip the inner work and move on to the next item." Without continue, the same logic needs a deeper-nested if — same behaviour, more indentation, harder to scan. Both continue and break accept loop labels (e.g., 'outer) so you can skip or exit an outer loop from inside an inner one.

   // continue — jump to the next iteration of the enclosing loop.
   for i in 0..10 {
       if i % 2 == 0 { continue; }       // skip even numbers
       println!("{}", i);                  // prints 1, 3, 5, 7, 9
   }
   
   // break — exit the loop entirely.
   for i in 0..10 {
       if i == 5 { break; }
       println!("{}", i);                  // prints 0, 1, 2, 3, 4
   }
   
   
   // Page 30's use — skip items that can't possibly fit:
   for &v in items {
       let v = v as usize;
       if v > t { continue; }              // item too big — nothing to update
       for s in (v..=t).rev() {
           if reachable[s - v] { reachable[s] = true; }
       }
   }
   
   // Equivalent without continue — same logic, deeper nesting:
   for &v in items {
       let v = v as usize;
       if v <= t {
           for s in (v..=t).rev() {
               if reachable[s - v] { reachable[s] = true; }
           }
       }
   }
   // continue flattens the structure — the body stays at one indentation level.
   
   
   // Labels for nested loops — break or continue a specific outer level:
   'outer: for i in 0..5 {
       for j in 0..5 {
           if j == 3 { continue 'outer; }   // skip the rest of THIS i
           if i == 4 { break 'outer; }      // exit the outer loop entirely
           println!("{} {}", i, j);
       }
   }

3. 03
   .rev() reverses an iterator, yielding the elements in the opposite order. On page 30, (v..=t).rev() walks s from t down to v instead of v up to t. It works only for iterators that implement DoubleEndedIterator — ranges, slices, VecDeque, and most ordered collections do; hash-map iterators and one-shot streams do not. The reason this specific DP needs reverse order is a classic subset-sum trick. When the loop marks reachable[s] = true because reachable[s - v] was true, it must be reading reachable as it was before the current item was considered — otherwise we would accidentally use the same item twice (counting it once at s - v and again at s). Iterating from t downward guarantees every read of reachable[s - v] sees an entry not yet touched in this pass, preserving the "include this item zero or one time" rule of 0/1 subset sum. Forward iteration would silently turn the function into unbounded subset sum, where every item can be used any number of times.

   // .rev() reverses an iterator.  Works for any DoubleEndedIterator.
   let r = (1..=5).rev();
   let v: Vec<i32> = r.collect();           // [5, 4, 3, 2, 1]
   
   
   // Page 30's use — walk s from t down to v:
   for s in (v..=t).rev() {
       if reachable[s - v] { reachable[s] = true; }
   }
   
   // What changes vs forward iteration:
   //
   //   Forward (v..=t)              reachable[s - v] read AFTER it was updated
   //                                this same pass → item used multiple times
   //                                → solves UNBOUNDED subset sum (different problem)
   //
   //   Reverse (v..=t).rev()        reachable[s - v] always reads an entry not
   //                                yet touched this pass → item used at most once
   //                                → solves 0/1 subset sum (the page 30 problem)
   
   
   // Worked example.  items = [3], target t = 6.
   // Initial:  reachable = [T, F, F, F, F, F, F]      (only sum=0 is reachable)
   
   // Iterate FORWARD (s = 3, 4, 5, 6):
   //   s=3: reachable[0]=T → reachable[3] := T
   //   s=4: reachable[1]=F
   //   s=5: reachable[2]=F
   //   s=6: reachable[3]=T → reachable[6] := T        ← BUG: 6 = 3 + 3, used twice
   //   final: [T, F, F, T, F, F, T]
   
   // Iterate REVERSE (s = 6, 5, 4, 3):
   //   s=6: reachable[3]=F                            (not yet updated this pass)
   //   s=5: reachable[2]=F
   //   s=4: reachable[1]=F
   //   s=3: reachable[0]=T → reachable[3] := T
   //   final: [T, F, F, T, F, F, F]                   ← correct 0/1 result
   
   
   // Other DoubleEndedIterator combinators worth knowing:
   let v = vec![1, 2, 3, 4, 5];
   
   v.iter().rev().for_each(|x| print!("{} ", x));     // 5 4 3 2 1
   v.iter().next_back();                               // Some(&5) — back without rev()
   v.iter().rfind(|&&x| x > 2);                        // Some(&5) — find from the back
   
   
   // HashMap iterators are NOT DoubleEndedIterator — order is hash-defined,
   // so "reverse" has no meaning:
   let map: HashMap<&str, i32> = /* ... */;
   // map.iter().rev();   // error — DoubleEndedIterator not implemented