Здравствуйте, Nelud, Вы писали:

N>OK, но если у нас n чисел и надо делить на k где k>n то тогда ...

Тогда, в общем случае, задача будет очень похожа на NP-сложную. Я не смог пока этого доказать. Можно посмотреть книгу Гери и Джонсона, в которой описано много известных задач и дана мотивация их принадлежности/непринадлежности классам NPC/NPH. Однако, в некоторых случаях, эту задачу можно будет решить эффективно. Например, при N>=K, или при K=N+1 можно реализовать квадратичный алгоритм, который будет выкидывать каждый из элементов исходного множества, и потом применять описанную идею для массива без элемента (то же самое и для K=N+2, K=N+3...; только выкидывать прийдется по два, три, ... элемента, что будет каждый раз увеличивать сложность на порядок).

Так что, похоже, на счет рюкзачного алгоритма умный человек был прав. Особенно если он имел ввиду backtracking. В таком случае нужно смотреть те материалы, которые были предложены.