Powerset

Powerset_flatMap.swift

extension Array {
	var powerSet: [[Element]] {
		guard !isEmpty else { return [[]] }
		return Array(self[1...]).powerSet.flatMap { [$0, [self[0]] + $0] }
	}
}

print([1,2,3,4].powerSet) // -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Powerset_map.swift

extension Array {
	var powerSet: [[Element]] {
		guard !isEmpty else { return [[]] }
		let tailPowerSet = Array(self[1...]).powerSet
		return tailPowerSet.map { [self[0]] + $0 } + tailPowerSet
	}
}

print([1,2,3,4].powerSet) // -> [[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]

what is complexity of power set algorithm it seems to growth hugely in my case like O(n!) or O(n^k)