It looks like you're trying to do some sort of divide-and-conquer that you might find in a sorting algorithm. Sorting and taking the second value from the large end would work, but it's overkill for this problem because you don't really need to have the set of elements sorted when you're done.
The brute-force solution is O(n-1), does at most 2*(n-1) comparisons and occupies space equivalent to two of your set members:
l1 := first_member_in_set -- Largest value
l2 := first_member_in_set -- Second-largest value
for each set member m after the first
if m > l1
l2 := l1
l1 := m
else if m > l2
l2 := m
end if
end for
Note that for this to work (and for there to be a second-largest member at all), the set must have at least two members.
Define a recursive function that takes an array of values and will generate a list of all the trees we want.
When the function receives just one value, it should return a list containing as it's sole element that value.
When the function receives two values, it should returns list containing as it's sole element the op of those two values in order.
When the function receives more than two values, it should keep a list to return, and iterate through the indices between the members of the array. For each index between members of the array, split the array into a left array and a right array based on the index. Recurse on these arrays, generating the list of trees for each. Then take the cross product of the lists this generated and add it to the list to return.
The way this works is that for any array of more than two values, we can split it multiple ways. For each way to split the array, there is at least one possible tree on the left side, and at least one possible tree on the right side. Each combination of possible trees on the right and left sides is a possible tree.
Edit: Here's some pseudo code (roughly Java/python):
List<Tree> getOpTrees(List<Value> values):
if (length(values) == 1):
return new List(new IdentityTree(values[0]))
if (length(values) == 2):
return new List(new OpTree(values[0], values[1]))
treeList = new List<Tree>()
for (index from 1 to length(values)-1):
leftList, rightList = values.split(index)
for (leftTree : getOpTrees(leftList)):
for (rightTree : getOpTrees(rightList)):
treeList.add(new OpTree(leftTree, rightTree))
return treeList
Actually, I don't think we even need the n=2 base case. If n=2, we will only ever have index=1. Then we split the left and right lists, which will each have exactly one element. They will each return a single element list containing the identity tree of their element. Then the only thing added to treeList will be OpTree of the two IdentityTrees.
Best Answer
Lets take an array of size
n. There 2n possible subarrays of this array. Lets take the example array of size 4:[1, 2, 3, 4]. There are 24 sub arrays.Sub array of the empty set (
[]) is the 0th one (0000). The subarray of[1], is the second one (0001), the subarray of[2]is the second one... (0010) and the subarray[1, 2]is the third one (0011). You should see where this is going.No recursion is necessary for this. The set of the sub arrays is the binary representation of the the nth value ranging from 0 to 2n - 1.
With this realization, the generation of all of the subarrays for a given arrays should be a trivial matter of iterating of the integers and looking at them as bit fields for if a particular element is in the subarray or not.
See also Number of k combinations for all k on Wikipedia.
I would point out that this is probably the right way to do it in C and similar languages. Trying to force recursion, lists, and backtracking onto what would otherwise be a simple iterative problem with a clear and understandable answer may not the best approach.
Note that other proposed answers to this quickly become functional programming examples and solutions. Functional programming is great. However, in a language not suited for such trying to force this paradigm of programming on it would be akin to writing C code in Lisp - it might not be the best way to approach the problem.
I should further point out that the problem hinted at in the question is:
This is a well known problem known as the subset sum problem and has a number of approaches to solve it... generating all the subsets of the array is not required (or even desired) for the faster approaches to solve it.