So I have a situation where I have two separate arrays with an integer value in each,

pre = [ {5}, {4}, {15}, {12}, {8}, {13} ]
suf = [ {12}, {0}, {17}, {3}, {9}, {11} ]

and I have a number, ie. 44, that I want to calculate all the possible additions of both arrays to equal 44.

ie. pre {15} + suf {12} + {suf}17 = 44.

However I want a minimum of 3 and a maximum of 6 to be used to reach this total, and I don't want to use anything twice (per match, ie to get 16 don't use pre = {8} + pre = {8}), I've tried a number of things (for loops..) however nothing works out too well.
I know it's a pretty specific and difficult thing to achieve

This is what I'm currently using which I know really obviously won't achieve what I want exactly but it's a start.


Thanks.

E:\ I'm wanting to learn so pointing me in the right direction is preferable

This post was edited by Ministry on Dec 21 2013 03:42am

i don't see any reason to have two arrays, so just combine them into a single sorted array to make things easier.

have 3 pointers i = 0, j = 1, k = 2. since you want 3-6, i recommend using an array instead of 3 actual variables so you can loop it since the logic is the same. add up array[i] + array[j] + array[k]. if it's too low, k++ and try again. once you go over, set j++ and k = j + 1. repeat until you go over, then set i++ and j = i+1 and k = j+1. repeat until everything's covered. make sure i, j, k are never equal to each other. visually, all your pointers start on the left of your array. once they all migrate to the right, you're done. make sure your algorithm checks every possible pair until it goes out of bounds. at that point it can be pruned since your array is sorted. if your integers can be negative, you'll have to take that into account.

ex if you had 5 elements, your 3-element-check would hit these indexes ijk format:
012
013
014
023
024
034
123
124
134
234

this is a brute force approach. if you're doing this for an interview or something, you can be more clever. eg if you have i and j set, there's only one possible value (plus duplicates) for k. so instead of scanning the whole array you could do a binary search from index j+1 to n-1 where n is the size of the array. alternatively, you can create another array(s) which contains sums of certain indexes. i'm sure there are other ideas too. it's a common interview question so google around and adjust their algorithms for your need. but brute force is probably the easiest to understand/code for you.

This post was edited by carteblanche on Dec 21 2013 07:31am

The separate arrays are for a prefix and suffix list-- it works perfectly fine when I only need 1 from each list, it's just expanding that into a 3-6 unique match. I tried using the .splice(i, 1) which removes an affix when it uses it (good unique usage) then once it's done it's forloops and met the clause (the ie number 44) reset the array and go again. Maybe I could use a list, verify it's >=3 or <=6 before pushing it as a successful result?

i'm still not clear what the significance of prefix and suffix is. your description of the problem didn't include anything about it.

It can only have a max of 3 prefix and 3 suffix, if I put them into one array I'll have to add another value to differentiate between a suffix and a prefix.

would have been nice to know that in the OP. luckily it doesn't change much since the brute force algorithm basis is the same.

use these # of pointers for prefix,suffix
0,3
1,2
1,3
2,1
2,2
2,3
3,0
3,1
3,2
3,3

might be easier to pass an array whose size corresponds to the number of pointers for the corresponding array.

eg:



This post was edited by carteblanche on Dec 21 2013 10:00am