I write this question of behalf of quite a few of my friends who have faced a lot of problem with problems such as Paying Up(MARCH09). I come across quite a few problems in competitive coding competitions and problems where i have to check which elements of the array add up to a given certain number. For example, I have an array of 10 random integers and i have to find all those sub arrays (not necessarily with contiguous elements) which add up to 100. How would i do it? I need the all the sub-arrays, be it with 1 element or 10.Any guidance is highly appreciated. If you wish to type a code, please see if you can code it in JAVA(highly preferred and have decent command over it) or C or if not, then pseudocode. Also, please do tell me if it is possible to implement the solution without the use of slighly advanced concepts such as Stacks, queues, hash-maps (i don’t know much about these terms as i randomly come across them about them). Also is there any way to approach such problems? Also take the example of the 2nd problem of FaceBook Hacker Cup ‘New Year’s Resolution’. I’m honestly lost when it comes to problems like this.
Take a look at this
This problem is about subset sum.
For the given constraints (banknotes<1000) the solution is complete overkill. The dp approach is much better suited.
If the numbers are arbitrarily high (or bounded by say 10^9) the proposed approach would be sensible.