Minimal Subset that sums up to Let $X \subsetneq \mathbb{N}$ be a finite set, and $c \in \mathbb{N}$ we are looking for a subset
$$ Y \subseteq X $$
such that $\sum_{y \in Y} y \geq c$. Assuming a subset that satisfies the property exists, we trying to find one such that $\sum_{y \in Y} y$ is minimal.
How hard is this? Can we approximate?
 A: Let $X  = \{x_1, x_2, \dots, x_n\}$ where $x_i \in \mathbb{N}$
You can solve this deterministically using 0-1 Knapsack.
Let $dp(i,j) = 1$ denote that it is possible to create a sum of value $i$ using the first $j$ elements of $X$ and $dp(i,j) = 0$ denote that it is not possible.
Here, $i$ will vary from $0$ to $\sum_{x_i \ \in X}{x_i}$ and $j$ will vary from $0$ to $n$
The recurrence relation will be
$$dp(i,j) =
\begin{cases}
1 &\mbox{if } dp(i - x_j,j -1) = 1 \\ 
0 &\mbox{otherwise}
\end{cases}$$
Once we finish the computation, we just find the first $i \ge c$ for which $dp(i,j) = 1$ for some $j$
The overall time complexity will be $\mathcal{O}(n\sum{x_i})$
You can then recover the subset via backtracking.
A: You can make the assumption that $\sum_{x \in X} x \geq c$ in order for such a subset to exist. Then, consider the set $\mathcal{S}= \{ \sum_{y \in Y} y\ |\ Y \in \mathcal{P}(X)\ \mathrm{and}\  \sum_{y \in Y} y \geq c\}$. Since $\sum_{x \in X} x \geq c$, we know that $\mathcal{S}$ is a non-empty subset of the well-ordered set $\mathbb{N}$. Thus, there is a minimum of $\mathcal{S}$, say $m$. Then $m=\sum_{y \in Y_m} y$ for some subset $Y_m$ of $X$.
