0
$\begingroup$

The algorithm needs to generate all possible combinations from a given list (empty set excluded).

list          =>         [1, 2, 3]
combinations  =>         [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

This algorithm would take O(2n) time complexity to generate all combinations. However, I'm not sure if an improved algorithm can bring this time complexity down. If an improved algorithm exists, please do share your knowledge!

In the case that it takes O(2n) which is exponential, I would like some insight regarding which class this algorithm belongs to P, NP, NP-Complete, NP-Hard, or whether it does not belong to any of them. Thanks in advance :)

$\endgroup$
2
$\begingroup$

If you want to explicitly list all subsets of list, then the size of the output will be $\Omega( n \cdot 2^n )$. Notice indeed at least half of these subsets have at least $\lfloor n/2 \rfloor$ elements, and just writing them out requires $\Omega( n \cdot 2^n )$ space (and time).

If you want to iterate over each of these subsets but you don't necessarily need to explicitly list them, then you still need $\Omega(2^n)$ time since there are $2^n - 1$ subsets of interest.

An easy algorithm is as follows: maintain a binary counter $c$ of $n$ bits. Intuitively, the counter represent the indicator vector of a subset $X$ of list (i.e., the $i$-th bit is $1$ iff the $i$-th element of list is included in $X$). Initially $c=0$. Increment $c$ until it overflows. Each time that a bit flips from $0$ to $1$ (resp. $1$ to $0$) you interpret this as adding (resp. removing) the corresponding element to $X$. The set resulting after each increment is the next set to consider.

This algorithm requires $O(2^n)$ time, plus whatever time you need to process these implicitly generated sets. To see this you can take a look at the amortized analysis of incrementing a binary counter (see, e.g., the section "Incrementing a binary counter" in Chapter 17 of CLRS). Essentially, the least significant bit flips at every increment, the second least significant bit only flips every other increment, and so on. The number of bit flips is then $\sum_{i=0}^{n-1} \frac{2^n}{2^i} < 2^n \cdot \sum_{i=0}^{+\infty} 2^{-i} = 2^{n+1} = O(2^n)$.

An application of this algorithm is generating all possible subset-sums of a set $S$ of integers (which is used used, e.g., in the split-and-list algorithm for the subset-sum problem), assuming that $\sum_{x \in S} x$ still fits into a constant number of memory words (and hence arithmetic operations can be carried out in constant time). In this case adding (resp. removing) an element $x$ to the subset simply means increment the previous sum by $x$ (resp. $-x$).

Asking whether this problem belongs to $\textsf{P}$ or $\textsf{NP}$ or is $\textsf{NP}$-complete makes no sense, since these complexity classes are only defined for decision problems (and yours is not).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.