# 35.5 The subset-sum problem

## 35.5-1¶

Prove equation $\text{(35.23)}$. Then show that after executing line 5 of $\text{EXACT-SUBSET-SUM}$, $L_i$ is a sorted list containing every element of $P_i$ whose value is not more than $t$.

(Omit!)

## 35.5-2¶

Using induction on $i$, prove inequality $\text{(35.26)}$.

(Omit!)

## 35.5-3¶

Prove inequality $\text{(35.29)}$.

(Omit!)

## 35.5-4¶

How would you modify the approximation scheme presented in this section to ﬁnd a good approximation to the smallest value not less than $t$ that is a sum of some subset of the given input list?

(Omit!)

## 35.5-5¶

Modify the $\text{APPROX-SUBSET-SUM}$ procedure to also return the subset of $S$ that sums to the value $z^*$.

(Omit!)