text: Для достижения этого мы имеем следующие рекуррентные формулы: p(i, j) принимает значение True, если либо p(i, j − 1) принимает значение True, либо p(i − xj, j − 1) принимает значение True p(i, j) принимает значение False в противном случае Причина этому следующая: существует некоторое подмножество S, сумма которого равна i для чисел x1, ..., xj тогда и только тогда, когда одно из двух верно: существует подмножество { x1, ..., xj-1 }, дающее сумму i; существует подмножество { x1, ..., xj-1 }, дающее сумму i − xj, поскольку xj + сумма этого подмножества=i.