выбор между подмножеством данных

Question

предположим, у меня есть {a,b,c} между их подмножествами:

SUB={{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

Я хочу иметь полные члены в массиве, например:

array[0]={{a,b,c}}

array[1]={{a,b},{c}}

array[2]={{a},{b,c}}

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

. Я хочу сократить время сложности, если я буду искать по целому, это будет n * n, но я думаю, что рекурсивное написание уменьшитсложность времени, но я не могу решить, как кодировать рекурсивную.этот пример был с 3 членами, я хочу его для n членов.

Я знаю, как извлечь подмножества, но я не знаю, как заполнить мой массив с этим условием.

Answer 1

Рекурсивный алгоритм не влияет на сложность.Любой рекурсивный алгоритм может быть реализован с помощью эквивалентного итеративного алгоритма (Теория вычислений 101).

Если у вас нет предварительных знаний (например, знание того, что он отсортирован, как в вашем примере, может помочь.это, конечно), у вас нет выбора, кроме как пройти через все из них (в худшем случае).