سوال ۵۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

Each element of a sequence of length $n$ can be either included in a subsequence or left out — two independent binary choices per element.

Hence the total number of subsequences equals the size of the power set of the index positions:

$\underbrace{2 \times 2 \times \cdots \times 2}_{n\text{ factors}} = 2^{n}.$

A backtracking enumeration builds a binary recursion tree: at each of the $n$ levels it branches on "take / skip" the current element. The tree therefore has $2^{n}$ leaves, one per subsequence, so the algorithm performs $\Theta(2^{n})$ work just to produce them all.

Therefore the time complexity is

$O(2^{n}).$

The other options are wrong: $O(n^{2})$ and $O(\log n)$ are far too small to even list $2^{n}$ outputs, and $O(n!)$ counts permutations / orderings of $n$ items, not subsets.

Exam trick: Subsequences (subsets) $\Rightarrow 2^{n}$; permutations (orderings) $\Rightarrow n!$. Any algorithm that must output every member of such a family cannot beat the size of the family itself.