_Case,

Пусть A - исходный массив длины N. Выпишем его в форме вектора:

A = [a(1), ..., a(N)]

Для каждой группы запишем характеристический вектор X
-если элемент a(i) принадлежит группе, x(i) = 1, в противном случае - 0

например, для группы из элемента а(1) вектор будет иметь вид:
X({a(1)}) = [1,0,.....,0]
а X({a(1),a(2)}) = [1,1,0,....0]

Очевидно, что множество характеристических векторов взаимно-однозначно отображается на множество подмножеств исходного массива, и каждый X-вектор является записью двоичного числа разрядности N (N-битный байт, двоичное число с дописанными нулями впереди).

Количество X-векторов в точности равно 2^n (если включать нулевой вектор, соответствующий пустой группе) или 2^n-1 (если вырожденный случай с пустой группой выкидываем).

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

X-векторы легко отсортировать в естественном порядке (от 0 до 2^N-1)
[0,0,...,0] (=0)
[0,0,...,1] (=1)
....
[1,1,...,1] (=2^n-1)

Это дает общую идею алгоритма:

ДЛЯ счетчик = 3 ПО 2^N-1 С ШАГОМ 1 ЦИКЛ
ЕСЛИ СтепеньДвойки(счетчик) Тогда
ПРОДОЛЖИТЬ; //уходим на следующую итерацию
ИНАЧЕ
БитоваяМаска = ЧислоВБитовуюМаску(счетчик,N);
Группа = ВыбратьГруппу(ИсходныйМассив, БитоваяМаска)
КОНЕЦ ЕСЛИ;
КОНЕЦ ЦИКЛА;

Потребуется разработать функции:

СтепеньДвойки -возвращает булевский тип; Можно сначала вычислить массив степеней, и проверять попадает ли очередное значение счетчика в этот массив.

Либо просто считать количество единиц в битовой маске (если 1 - то это степень двойки).

ЧислоВБитовуюМаску - тут все очевидно, для примера ЧислоВБитовуюМаску(3,5) = 00101
ВыбратьГруппу - функция должна выбирать из исходного массива элементы, соответствующие 1 в битовой маске.

Цикл начинаем с 3, потому что 0...01 (=1) и 0...010 (=2), очевидно, не подходят по условию задачи.

Надо иметь в виду, что 2^10*n ~10^n, т.е. при N>30 количество всех возможных групп переваливает за миллиард.

UPD. Исправляю неверную оценку в конце предыдущего поста, 2^10*n ~ 10^3*n, множитель в степени 10 забыл :)

Abstraction,

упорядоченные подгруппы на самом деле не рассматриваются, но мой ответ вообще неправильный.

Я не до конца понял условие задачи :(

Приведенный алгоритм позволяет выделить все группы c числом элементов => 2 , а надо же найти все годные разбиения.

Действительно, на ум приходит рекурсия :)