Subset Sum on Generated Sequence

Problem Overview

Start with s on the paper; each next number is (current total) + arr[i].

Intuition

Start with s on the paper; each next number is (current total) + arr[i]. That makes every new value at least the sum of all earlier ones, so the sequence is superincreasing-style and subset sum reduces to greedy from largest to smallest. Numbers grow exponentially, so only O(log x) terms matter. You can rebuild those terms from the final total while scanning arr backward instead of storing a list.

Algorithm

1If x == 0 return true (empty subset). If x == s return true. If x < s return false.
2total = s; for each a in arr, next = total + a; stop when next would exceed x; else total += next and count it.
3target = x. For i from last generated index down to 0: last = (total + arr[i]) / 2.
4If last <= target, subtract it from target (return true if target hits 0). Set total = (total - arr[i]) / 2.
5Finally return whether the remaining target equals s (take the initial number).

Example Walkthrough

Input: arr = [1, 2], s = 3, x = 7

1. Sequence: 3, then 3+1=4 (total 7), then 7+2=9 > 7 so stop. Numbers used: [3, 4].
2. Greedy on 7: take 4, left 3; take 3, left 0.
3. Possible.

Output: true

Common Pitfalls

• x == 0 must be true - do not reject it with an x < s check.
• Use long for totals; values roughly double each step and can overflow int.
• Stop generating when the next value would exceed x - later values only get larger.
• When reconstructing, last = (total + arr[i]) / 2 always divides evenly because total = 2*prev + arr[i].

Subset Sum on Generated Sequence.java

Java

// Approach: Sequence starts at s; each next value is (sum so far) + arr[i], so
// every new value is >= the sum of all earlier ones (superincreasing-style).
// Subset sum is then greedy from largest to smallest. x == 0 is true (empty
// subset). Generate until the next value would exceed x (at most O(log x)
// terms). Reconstruct those values from the final total while walking arr
// backward - no need to store the list.
// Complexity: O(min(n, log x)) time and O(1) extra space.

class Solution {

    public boolean isPossible(int[] arr, int s, int x) {
        // Empty subset sums to 0.
        if (x == 0 || x == s) {
            return true;
        }
        if (x < s) {
            return false;
        }

        long total = s;
        int k = 0;

        for (int a : arr) {
            if (a > x || total > (long) x - a) {
                break;
            }
            long next = total + a;
            total += next;
            k++;
        }

        long target = x;
        for (int i = k - 1; i >= 0; i--) {
            // total = 2 * prev + arr[i], last = prev + arr[i] = (total + arr[i]) / 2
            long last = (total + arr[i]) / 2;
            if (last <= target) {
                target -= last;
                if (target == 0) {
                    return true;
                }
            }
            total = (total - arr[i]) / 2;
        }

        return target == s;
    }
}

Was this solution helpful?