Sum of the series of numbers in an array

Question

You are given a number $x$ and an array A[1,2....n] storing $n$ positive numbers such that $$A[1]+A[2]+....+A[i]≤A[i+1], \space \forall i<1.$$ Design a polynomial time algorithm to determine if there exist $$1 ≤ i_1 < i_2 < ... < i_t ≤ n$$ such that $$A[i_1]+A[i_2]+...+A[i_t] = x.$$ If we permute all the combinations of $n$, taking sum of these combinations will leave us with $n^k$ combinations, and hence the running time will be $O(n^k)$. Is there any way to improve complexity?

Answer 1

Given the condition on the $A[i]$, this can be done very efficiently. Simply go backwards through the $A[i]$, incorporating each $A[i]$ into the sum if possible:

remaining := x
index_set := { }
for (i = n to 1)
    if (A[i] <= remaining)
        remaining := remaining - A[i]
        Add i to index_set
    end if

Then if remaining is zero, the solution is in index_set; if remaining is non-zero, there is no solution.