-1

I have an array, say

ar = [1,2,3,4,5]

I need to find a list of arrays (or a matrix) that contains an all possible ways to split this array into exhaustive sets of pairs.

eg. 

[
 [[1,2],[3,4],[5]],
 [[1,2],[3,5],[4]],
 [[1,2],[4,5],[3]],
 [[1,3],[2,4],[5]]
 ...
 [[1,5],[3,4],[2]]
                  ]

Please try to use pseudocode, or refrain from using language-specific functions

Paulo
  • 325
  • 3
  • 16
  • i do understand there may be a possible duplicate [here](https://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways), but it is specific to python, and use of implicit functions makes it difficult to understand – Paulo Jul 28 '17 at 04:00

1 Answers1

0

I will give the intuition to solve this type of question. First you can see that this problem can be solved recursively. Why is that?

First you take any two elements from the array,

Then you solve the same problem for the rest of the elements of the array.

If the length of the array is 2 or 1 you stop.

Following is a rough pseudo code.

solve(arr){
    if len(arr)==1 or 2{
        return arr
    }

    take two elements
    (say [1, 5])
    remainder = [2, 3, 4]
    solve(remainder)
}
smb564
  • 343
  • 1
  • 11
  • recursion is certainly one method. But it isn't efficient. Think array size 100 – Paulo Jul 28 '17 at 13:49
  • I just gave you the intuition. It is evident that many of the sub problems overlap. Hence we can go with memorized-recursion aka Dynamic Programming. – smb564 Jul 29 '17 at 02:43
  • I've thought about it.. but can you consider how you can use Dynamic Programming here? – Paulo Jul 29 '17 at 03:37