Question

What is the size of the set of all subsets of \(n\) elements in sum of subsets problem?

• A. \(n^2\)
• B. \(2\)
• C. \(n\)
• D. \(2^n\)

Hint:

A set with \(n\) elements has exactly \[ 2^n \] subsets.

Answer 1

The Correct Option is D

Concept: The Sum of Subsets problem belongs to the class of combinatorial optimization problems. For a set containing \(n\) elements, every element has two possibilities:
• Included in the subset
• Not included in the subset Thus each element contributes two choices.

Step 1: Determine choices for each element.
Suppose a set contains \[ \{a_1,a_2,\ldots,a_n\}. \] For every element \(a_i\), we have: \[ 2 \text{ choices} \] namely include or exclude.

Step 2: Apply multiplication principle.
Since choices are independent, \[ 2\times2\times2\times\cdots\times2 \] (\(n\) times) \[ =2^n. \]

Step 3: Interpret the result.
Hence the total number of subsets of an \(n\)-element set is \[ 2^n. \] This includes the empty set and the full set.

Step 4: Write the answer.
Therefore, \[ \boxed{2^n} \] Hence option (D) is correct.