Convert Array a[] to b[] by way of Subsequence addition

Given an array a[] equal = {1} and a goal array b[], the duty is to test whether or not you may rework a to b or not by performing an operation on array a[]. The operation is outlined as selecting any subsequence of array a and insert the sum of the numbers of the subsequence to the array a at any place.

Examples:

Enter: b[] = {5, 1, 3, 2, 1}
Output: Sure
Clarification: Initially, a = [1]
By selecting the subsequence [1], and inserting 1 within the array, a modifications to [1, 1]
By selecting the subsequence [1, 1], and inserting 1+1 = 2 in the midst of the array, a modifications to [1, 2, 1]
By selecting the subsequence [1, 2], and inserting 1+2 = 3 after the primary 1 of the array, a modifications to [1, 3, 2, 1]
By selecting the subsequence [1, 3, 1] and inserting 1+3+1 = 5 firstly of the array, a modifications to [5, 1, 3, 2, 1]

Enter: b[] = {7, 1, 5, 2, 1}
Output: No
Clarification: Initially, a = [1]
By selecting the subsequence [1], and inserting 1 within the array, a modifications to [1, 1]
By selecting the subsequence [1, 1], and inserting 1+1 = 2 in the midst of the array, a modifications to [1, 2, 1]
Now you may’t kind 5 from any subsequence

Method: To unravel the issue observe the beneath concept:

It may be noticed that if the primary component of b is just not 1, then the transformation is just not potential as as a way to generate all the opposite parts utilizing the given operation, the primary component of b have to be 1. Now we’ve got to test whether or not every component in b may be generated by including parts of a subsequence of arr. Now kind the array b and iterates by way of every component and test whether it is potential to generate the present component by including parts in subset of arr. If it’s not potential, then the transformation is just not potential. It’s because every component in b have to be generated utilizing the weather of arr as a way to rework arr to b.

Beneath are the steps for the above method:

• Type the goal vector.
• Test if the primary component of the goal vector is just not equal to 1, and return false.
• Initialize a variable say currentSum = 1.
• Iterate the goal vector from the second component and test if currentSum ≥ present component,
  • Add the present component to the present sum
• Else, return false. 
• If iteration over the goal vector is accomplished with out returning false, return true, indicating that the vector arr may be represented because the goal vector.

Beneath is the implementation for the above method:

Time complexity: O(n*logn)
Auxiliary House: 0(1)