Change the subset sum
An array of N positive integers is given. Let the minimum element be L and the sum of all elements be S.
I need to figure out if, for every integer X (where X is between L and S inclusive), one can select a subset of the array so that the sum of the elements in that subset equals X.
EXAMPLE:
Let it be an N=5
array {4,8,2,1,16}
. Then here all the elements can be made from 1 to 31, so here ans "yes".
Assuming an N=4
array {5,1,2,7}
. Then, for values from 1 to 15, the values 4 and 11 cannot be met. So the answer here is no.
source to share
I know to find the minimum number that this array cannot return. But not sure how to solve this problem.
First, does the array only have one element? If yes, then yes.
Otherwise, find the minimum impossible amount. Is it more than S? If yes, then yes. Otherwise, the answer will be no. (If the minimum is less than L, the array does not contain 1, and S-1 is an impossible sum.)
To find the smallest impossible sum, we sort the input, then find the smallest impossible sum of each prefix of the array. In Python:
def lowest_impossible_sum(nums):
nums = sorted(nums)
partial_sum = 0
for num in nums:
if num > partial_sum + 1:
return partial_sum + 1
partial_sum += num
return partial_sum + 1
Proof of correctness by induction:
Let A be a sorted array. If A[0] > 1
, then 1 is the smallest impossible sum. Otherwise, items A[:1]
can produce all amounts up to sum(A[:1])
.
Suppose for induction that subsets of A[:k]
can be chosen to create all sums up to sum(A[:k])
.
- If
A[k] > sum(A[:k]) + 1
, thensum(A[:k]) + 1
is the smallest impossible amount; it cannot be subsetA[:k]
and adding items not inA[:k]
will not help as they are too big. - If
A[k] <= sum(A[:k]) + 1
, then subsetsA[:k+1]
can produce each sum upsum(A[:k+1])
. Each sum tosum(A[:k])
can already be obtained by inductive hypothesis, and the sums fromsum(A[:k]) + 1
tosum(A[:k+1])
can be obtained by choosingA[k]
and a suitable subset ofA[:k]
addition to what is left.
Let x be the first index such that A[x] > sum(A[:x]) + 1
, or len(A)
, if there is no such index. Any sum up to is possible by induction sum(A[:x])
. However, since x is beyond the end of the array or because, it A[x] > sum(A[:x]) + 1
is impossible to get the sum sum(A[:x]) + 1
. Thus, we just need to search for x and return sum(A[:x]) + 1
. This is what the algorithm does.
source to share
First, sort all the elements of the array. If you want to get all values between L and S from the elements of the array, then L = 1 and the elements must be in the form 2 ^ i. And the largest element may not be of the form 2 ^ i, since the sum should not be of the form (2 ^ i - 1).
source to share