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;
}
}

Join the conversation! Your thoughts help the community grow.