Calculating this sum in $O(n)$ time
You can prove this by full induction, which gives you an algorithm, too. The claim is $$I_n = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} = (1 + a^{c_1})(1 + a^{c_2}) \ldots (1 + a^{c_n}) $$
The product of the right side can be computed in $O(n)$ steps if the exponentiation requires constant time.

Proof:


For $n=1$ the claim is obviously true: $I_1 = 1 + a^{\epsilon_1}$.
$n \rightarrow n+1$: Let the claim be true for $n$:
\begin{eqnarray}
(1 + a^{c_{n+1}})I_n &amp; = &amp; (1 + a^{\epsilon_{n+1}})\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 &amp; = &amp; \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} + a^{c_{n+1}}\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 &amp; = &amp; \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=0}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} + \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=1}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 &amp; = &amp; \sum_{(\epsilon_1,...,\epsilon_n,\epsilon_{n+1}) \in \{0,1\}^{n+1}}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 &amp; = &amp; I_{n+1}
\end{eqnarray}