Создавать комбинации заданной последовательности без рекурсии

1. По массиву уникальных чисел найдите комбинации
2. Выполнение полной копии кода, чтобы избежать изменений переданного объекта по ссылке
3. Это время выполнения $ O (n times text {#ofcombinations}) $ — можно ли это сделать лучше — итеративно и легко для понимания

import copy
def gen_combinations(arr): # 
    res = [[]]
    for ele in arr:
        temp_res = []
        for combination in res:
            temp_res.append(combination)
            new_combination = copy.copy(combination)
            new_combination.append(ele)
            temp_res.append(new_combination)
            res = copy.copy(temp_res)
        
    return res

Во-первых, примечание. Что вы называете combination обычно называется subset.

В комплекте $ n $ элементов средняя длина подмножества $ dfrac {n} {2} $. То есть создание одного подмножества требует $ O (п) $ время. Вы не можете получить временную сложность лучше, чем $ O (n2 ^ n) $.

Другое дело космическая сложность. Если вам действительно нужно все подмножество одновременно, то опять же сложность пространства не может быть лучше, чем $ O (n2 ^ n) $. С другой стороны, если вам нужно по одному подмножеству за раз, подумайте о преобразовании вашей функции в генератор, который yield подмножества по одному.

Более или менее канонический способ генерации подмножеств использует отображение подмножеств и чисел 1: 1. Каждый номер a в $[0, 2^n)$ range uniquely identifies subset of $n$ elements (and vice versa). Just pick the elements at the position where a has a bit set.

All that said, consider

def generate_subsets(arr):
    n = len(arr)
    for a in range(2 ** n):
        yield [arr[i] для i в диапазоне (n) if (a & (1 << i))! = 0]