You are given a list of numbers:
[28, 22, 7, 2, 8, 14, 24, 56]
Your task is to find the longest sub-set of this list, such that all of the items in the subset can be taken as pairs where the larger value of the pair is perfectly divisible by the smaller. For example, in the above list there is a sub-set {8, 2, 24}. This sub-set satisfies the “divisibility requirement” because all the pairings demonstrate perfect divisibility: 8/2 = 4, 24/8 = 3, and 24/2 = 12. However {8, 2, 24} is not the longest sub-list that can be found that satisfies the divisibility requirement. That would be: {7, 14, 28, 56}. Actually, there are multiple possible answers. Another would be: {2, 14, 28, 56}.
Write a program that finds the longest and “pair-wise divisible” sub-set of a given list of numbers. You should implement the following functions:
vector<int> largest_divisible_pairs(vector<int> input); string vec_to_string(vector<int> v);
Note, your program should work with any list that (a) contains only positive numbers and (b) does not contain any duplicate numbers. You may write a test() function, or you might hard-code a list into your main method. In either case, know that your program will be tested (graded) using a variety of input lists. In general your program only needs to output one solution, even when there are multiple solutions possible.
Pro-Tip: Using recursion to solve this problem is a good strategy.
Sample Output:
user@machine:solution$ ./ldp Input: [28 22 7 2 8 14 24 56]
Answer: [56 14 7 28]
