Smallest Integer Not Representable as Subset Sum

Given a non-decreasing sorted array ARR of N positive numbers, determine the smallest positive integer that cannot be expressed as the sum of elements from any proper subset of the array.

Example:

Input:

ARR = [1, 1, 3]

Output:

6

Explanation:

The possible sums of subsets are:
1 → [1]
2 → [1, 1]
3 → [3]
4 → [1, 3]
5 → [1, 1, 3]
The smallest integer not representable as a subset sum is 6.

Constraints:

1

Question

Smallest Integer Not Representable as Subset Sum

Given a non-decreasing sorted array ARR of N positive numbers, determine the smallest positive integer that cannot be expressed as the sum of elements from any proper subset of the array.

Example:

Input:

ARR = [1, 1, 3]

Output:

Explanation:

The possible sums of subsets are:
1 → [1] 
2 → [1, 1]
3 → [3]
4 → [1, 3]
5 → [1, 1, 3]
The smallest integer not representable as a subset sum is 6.

Constraints:

1 <= T <= 100
1 <= N <= 10^4
0 <= arr[i] <= 10^9

Accepted Answer

Find the smallest positive integer that cannot be expressed as the sum of elements from any proper subset of a non-decreasing sorted array of positive numbers.

Start with the smallest possible sum that can be represented, which is 1.
Iterate through the array and update the smallest sum that cannot be represented.
Return the final smallest sum that cannot be represented.