Introduction
The Subset Sum problem usually asks whether a target value can be obtained by selecting some elements from an array. A normal subset-sum problem can require dynamic programming and may take O(n × x) time.
However, this problem has a special generated sequence that allows us to solve it efficiently using a Greedy Algorithm.
Given an array arr[] and an initial value s, each child adds their arr[i] to the sum of all numbers currently written on the paper.
We need to determine whether the target x can be formed by selecting some numbers from the generated sequence.
Problem Understanding
Suppose:
arr = [1, 2, 4, 2]
s = 1
x = 7
The first number is:
1
The first child calculates:
1 + 1 = 2
The second child sees:
1 + 2
and writes:
5
The third child sees:
1 + 2 + 5
and writes:
12
The fourth child sees:
1 + 2 + 5 + 12
and writes:
22
Therefore, the generated sequence is:
1, 2, 5, 12, 22
Now we need to determine whether 7 can be formed.
2 + 5 = 7
Therefore:
true
Key Observation
The most important observation is that every generated number is larger than the sum of all previous generated numbers.
For the example:
1
2
5
12
22
Notice:
2 > 1
5 > 1 + 2
12 > 1 + 2 + 5
22 > 1 + 2 + 5 + 12
This property is what makes the greedy solution possible.
Because every number is greater than the sum of all previous numbers, we can process the sequence from largest to smallest.
Generating the Sequence
We maintain a variable called sum.
Initially:
long sum = s;
The first generated number is already s.
For every arr[i]:
long current = sum + arr[i];
Then we add the generated number to the total:
sum += current;
So the code becomes:
long[] seq = new long[arr.length + 1];
seq[0] = s;
long sum = s;
for (int i = 0; i < arr.length; i++) {
long current = sum + arr[i];
seq[i + 1] = current;
sum += current;
}
Step-by-Step Example
Consider:
arr = [1, 2, 4, 2]
s = 1
Initially:
sum = 1
Step 1
arr[0] = 1
Calculate:
current = 1 + 1
= 2
Now:
sequence = [1, 2]
sum = 1 + 2 = 3
Step 2
arr[1] = 2
Calculate:
current = 3 + 2
= 5
Now:
sequence = [1, 2, 5]
sum = 3 + 5 = 8
Step 3
arr[2] = 4
Calculate:
current = 8 + 4
= 12
Now:
sequence = [1, 2, 5, 12]
sum = 8 + 12 = 20
Step 4
arr[3] = 2
Calculate:
current = 20 + 2
= 22
Final sequence:
[1, 2, 5, 12, 22]
Why Do We Traverse from Right to Left?
Suppose:
sequence = [1, 2, 5, 12, 22]
target = 7
Start from the largest value.
Check 22
22 > 7
We cannot use it.
Skip it.
Check 12
12 > 7
Skip it.
Check 5
5 <= 7
Take 5.
Remaining target:
7 - 5 = 2
Check 2
2 <= 2
Take 2.
Remaining:
2 - 2 = 0
Therefore:
true
Complete Java Code
class Solution {
public boolean isPossible(int[] arr, int s, int x) {
long[] seq = new long[arr.length + 1];
// First number written on the paper
seq[0] = s;
// Sum of all numbers currently on the paper
long sum = s;
// Generate the sequence
for (int i = 0; i < arr.length; i++) {
long current = sum + arr[i];
seq[i + 1] = current;
// Add the newly generated number
// to the total sum
sum += current;
}
// Target that still needs to be formed
long target = x;
// Process from largest to smallest
for (int i = seq.length - 1; i >= 0; i--) {
if (seq[i] <= target) {
target -= seq[i];
}
// Target completely formed
if (target == 0) {
return true;
}
}
return false;
}
}
Code Explanation
1. Create the sequence array
long[] seq = new long[arr.length + 1];
There are n children, but the initial value s is also part of the sequence.
Therefore, we need:
n + 1
positions.
We use long because the generated values can become very large.
2. Store the initial value
seq[0] = s;
The initial number on the paper is s.
For example:
s = 1
So:
seq = [1, ...]
3. Maintain the total sum
long sum = s;
sum represents the sum of every number currently written on the paper.
Initially:
sum = s
4. Generate each number
long current = sum + arr[i];
The child adds arr[i] to the total of all previous numbers.
For example:
sum = 8
arr[i] = 4
Then:
current = 8 + 4
= 12
5. Add the generated number to the total
sum += current;
If:
sum = 8
current = 12
then:
sum = 20
This is important because the next child uses all numbers currently on the paper.
Greedy Part
After generating the sequence, we have:
1, 2, 5, 12, 22
We start with:
long target = x;
Then:
for (int i = seq.length - 1; i >= 0; i--)
means we process:
22 → 12 → 5 → 2 → 1
6. Take the current number if possible
if (seq[i] <= target) {
target -= seq[i];
}
If the current number does not exceed the remaining target, we select it.
For:
target = 7
seq[i] = 5
we get:
target = 7 - 5
= 2
7. Check whether target became zero
if (target == 0) {
return true;
}
Once the remaining target becomes 0, we have successfully formed x.
Why Greedy Is Correct
The generated sequence has this property:
current number > sum of all previous numbers
Therefore, when processing a number v:
Case 1: v > target
We cannot select v, because it is already larger than the remaining target.
So we skip it.
Case 2: v <= target
We should select v.
Why?
Because every smaller number together has a total smaller than v.
Therefore, if we don't take v, the smaller numbers cannot replace it when the target requires that amount.
This special property eliminates the need for traditional subset-sum DP.
Second Example
Consider:
arr = [51, 88]
s = 100
x = 500
Generate the sequence.
Initially:
100
First child:
100 + 51 = 151
Second child:
100 + 151 + 88 = 339
Sequence:
100, 151, 339
Now process from right to left:
target = 500
Take 339:
500 - 339 = 161
Take 151:
161 - 151 = 10
Take 100:
100 > 10
Skip it.
No number can make the remaining 10.
Therefore:
false
Why We Use long
The constraints allow:
arr[i] <= 10^9
s <= 10^9
But the generated sequence grows extremely quickly.
For example:
1
2
5
12
...
With up to 10^5 elements, the values can become far larger than the range of Java int.
Therefore, use:
long
instead of:
int
for:
Complexity Analysis
Time Complexity
Generating the sequence takes:
O(n)
The greedy traversal also takes:
O(n)
Overall:
O(n)
Space Complexity
We store the generated sequence:
O(n)
Therefore:
Time = O(n)
Space = O(n)
This matches the expected complexity.
Important Takeaway
This problem looks like a normal Subset Sum problem, but using standard DP would be unnecessary and too expensive because x can be as large as 10^9.
The crucial observation is:
Every newly generated number is greater than the sum of all previously generated numbers.
Because of this property, we can:
Generate the sequence in O(n).
Traverse it from largest to smallest.
Greedily subtract numbers that are not greater than the remaining target.
Return true if the target reaches zero.
So the main technique used here is:
Special Property of Sequence + Greedy Algorithm = O(n) Solution.