How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?
First, separate the set of variables $I = \{1,\dots,n\}$ according to their values:

$\qquad\begin{align}
  I_+ &amp;= \{ i \mid X_i = 1\} \text{ and} \\
  I_- &amp;= \{ i \mid X_i = 0\} \;.
\end{align}$

Let $n_+ = |I_+|$ and $n_- = |I_-|$.

Given $X_1, \dots, X_n$ and $k$, it is clear that we have to choose $k$ indices from $I_+$ and arbitrarily many from $I_-$. That means we will have to output

$\qquad \binom{n_+}{k} \cdot 2^{n_-}$

solutions. Note that if we assume $\binom{a}{b} = 0$ for $b&lt;0$ and $b&gt;a$, this extends nicely to inputs that allow no solution.

Generating all valid solutions in a list can be done by two nested recursions: the outer creates all $k$-subsets of $I_+$, the inner all subsets of $I_-$. This way, no illegal solutions are investigated, which is as efficient as you can expect (up to list operations).

  outer(I+, 0, I-) = inner(I-)
| outer(I+, k, I-) =
    result = []
    foreach ( i in I+ ) {
      suffices = outer(I+ - i, k-1, I-)
      result ++= (suffices map { [i] ++ _ })
    }
    return result

  inner([])      = []
  inner(x::rest) = 
    smaller = inner(rest);
    return smaller ++ (smaller map { [x] ++ _ })


If you want an iterator, note that you can replace recursion with stacks (which allows you to compute it step by step) and emit solutions in the innermost call of inner. Of course, you'll have to reverse the way solutions are constructed (while descending, as opposed to during ascension as I did above).