Question

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A)

What is the best way of finding the smallest number ($S$) that can't be obtained from the sum of any subset of C?

i.e.
if $A=\emptyset$, the smallest number $S= 1+\sum_1^Nx$,
but if $A\ne \emptyset,\ S\leq 1+ \sum_1^Nx-\sum_{i=0}^na_i$,
However if $N=10,A=\{2\}$, then $S=2$, and that is something that I'm not sure how to get efficiently.

I can obviously bruteforce the solution, but I can't find a better way, and I don't know how these kinds of problems are called so that I could Google them.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top