I was trying to solve the following problem.
We are given N and A
N <= 5000 A <= 10^6 and even if i is odd then A[i] >= 3 * A[i-1] if i is even A[i]= 2 * A[i-1] + 3 * A[i-2] element at odd index must be odd and at even it must be even.
We need to minimize the sum of the array.
and We are given a Q numbers
Q <= 1000 X<= 10^18
We need to determine is it possible to get subset-sum = X from our array.
What I have tried,
Creating a minimum sum array is easy. Just follow the equations and constraints.
The approach that I know for subset-sum is dynamic programming which has time complexity sum*sizeof(Array) but since sum can be as large as 10^18 that approach won't work.
Is there any equation relation that I am missing ?