power set

RU: степенное множество

The set of all subsets of a given set, including the empty set and the set itself. A set of n elements has 2ⁿ subsets. Generating the power set via backtracking — at each element deciding include or exclude — takes O(n · 2ⁿ) time, since there are 2ⁿ subsets and copying each costs O(n).