My idea is say the tube has 1,2,2,3 so I will try out (1,2), suppose their combination produces 2, now I've two options, taking 2 (which I got from (1,2)) and combine it with either 2 or 3 (from the remaining tubes) or combining remaining tubes (2,3), get their combination and try out with 2. Afterwards, I'll try out another combination from the beginning and this goes on.
Initially, I overlooked the fact that I can try out combinations from tubes remaining despite using one of the reagents from the combination formed from two tubes. So, I coded a solution, of course it is buggy. But now I am facing problems in implementing what I just have explained. Any help is really appreciated.
Problem link: https://uva.onlinejudge.org/external/106/10604.pdf
Buggy solution link: http://ideone.com/h2nMTX
I tried this problem the same way as you did, but I couldn't make it work properly...
Instead, I made a DP where the state was the amount of each chemical available at a moment. For example, if you have five chemicals, and seven tubes: 1 2 2 3 4 5 5, the DP state is {1,2,1,1,2} (from left ro right). This way, I try all the pair combinations of chemicals. Suppose that, mixing the chemicals of type 1 and type 2 produce a type 4 chemical, then:
Note that, I mixed chemicals (1,2), so I must subtract one from chemicals 1 and 2, and increase the amount of chemicals of the fourth type by one.
Base case: Only one chemical remains.
But, how to represent this state?
Note that, you will have at most 6 chemicals, so you can represent the state with a 6-length integer, where each digit represent the amount of a chemical (for example, one representation of the state I previously explained, could be the integer 12112, or 21121)
But, how to handle the case where we have 10 or more chemicals of the same type?
You will have at most 10 tubes, so the worst case is having 10 chemicals of the same type, nothing more. Although that state can't be represented, this case can be easily handled without the DP.