2010-8 第1問 (3)

全ての商品の価格の総和がq_min以下であるとき、ステップ4における集合S'は選択された要素を除いた後のSと等しいため、再帰呼び出しされるback手続き内でのback手続きの呼び出し回数は最大となる。
また、解が存在しないことからこのback手続きはSが空になるまで続けられる。

以上から、全ての商品の価格の総和がq_min以下であるときback手続きの呼び出し回数は最大となる。

このback手続きから直接呼び出されるi回目のback手続きの第二引数の要素数はl-iなので、
t_l = 1 + Σ_i=0^l-1t_i
となる。