Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$
Now let a good sequence be minimally good if it does not dominate any other good sequence. By dominate, I mean sequence $(a_1,a_2,\ldots,a_n)$ dominates $(b_1,b_2,\ldots,b_n)$. If $a_i \geq b_i$ for all $i$.
Is there anything interesting we can say about minimally good sequences? In particular, for a given $n$ and $k$, how many MSGs are there? Is there a formula for calculating MSGs? Is there a good algorithm for finding MSGs and what is its time-complexity?
As discussed in the comments, here's a solution to the problem without the restriction to odd sums.
If a sequence is minimally good, we cannot reduce any of the $a_i$, so there must be at least one sum that exactly equals $k$. Then the element not included in that sum must equal the greatest element included in the sum: If it were greater, we could reduce it by $1$ without harm, and if it were lesser, the sum that includes it instead of the greatest element would be less than $k$.
Thus, a minimally good sequence has $n-1$ elements that add up to $k$, and then another copy of the greatest of those elements. The tricky part is how to count such sequences without double-counting.
Let $j\ge2$ be the number of times the greatest element $m$ occurs. Then the remaining elements must sum to $k-(j-1)m$. There are $\binom nj$ positions for the greatest elements, and the possibilities for the remaining elements, which must all be less than $m$, can be calculated using the formula for balls in bins with limited capacity (which can be derived via inclusion-exclusion). Then the number of minimally good sequences is
$$ \sum_{m=1}^k\sum_{j=2}^n\binom nj\sum_{t=0}^{n-j}(-1)^t\binom{n-j}t\binom{n-j-1+k-(t+j-1)m}{n-j-1}\;, $$
where, following the page linked to above and contrary to convention, the binomial coefficients are taken to vanish when the upper index is less than the lower index.
If you add the restriction to odd sums, things get messy, since the sum can now be $k$ or $k+1$, and depending on details the element not included in the sum can be equal to the greatest element included in the sum or one more or one less than that.