Java Recursion on an ArrayList

Question

I have an ArrayList of int.

The main program - calls a method to get a list of the sum of all (n member) combination of the members of the list. Where n can be anywhere between 2 - 6. E.g. Original List is {1,2,3,4,5}; Then the output should be {6, 7, 8, 8, 9, 10, 9, 10, 11, 12} where n = 3;

I am looking for the optimum way to do this. Right now, the way I have written the program (which is working) is without recursion. I have methods for all numbers i.e.

MyMethod2 -- gives me all the sum of 2 member combinations of MyArrayList
MyMethod3 -- gives me all the sum of 3 member combinations of MyArrayList
MyMethod4 -- gives me all the sum of 4 member combinations of MyArrayList
......

So, you can see that there is a lot of duplicate set of codes.

Also the way the program has currently been written (e.g. My Method3):

MyMethod3
ArrayList<Integer> sum = new ArrayList<Integer>();
for (i = 0; i < MyArrayList.size(); i++){
    for (j = i + 1; j < MyArrayList.size(); j++){
        for (k = j + 1; k < MyArrayList.size(); k++){
            int total = MyArrayList.get(i) + MyArrayList.get(j) + MyArrayList.get(k);
            sum.add(total);
        }
    }
}
return sum;

The MyMethod for n = 6, can become pretty long. Also "n" can change in the future.

Is there a better way to do this using recursion to minimize duplicate code, and using the number n as a variablefor the method call. Is there a standard package in Java that can help with recursion.

Adding the Code based on @Maertin suggestion - which worked for me

    ArrayList<Integer> myArray = new ArrayList<Integer>();
    myArray.add(5);
    myArray.add(6);
    myArray.add(4);
    myArray.add(2);
    myArray.add(1);

    ArrayList<Integer>  finalSumArray = combineTwoArrayList(3, myArray, myArray);

public static ArrayList<Integer> combineTwoArrayList(int n, ArrayList<Integer> origArray, ArrayList<Integer> finalSumArray) {

    if (n == 1)  return finalSumArray;

    ArrayList<Integer> finalSumArray = new ArrayList<Integer>();

    for (int i = 0; i < sumArray.size() - 1; i++){
        for (int j = i + 1; j < origArray.size(); j++){

            finalSumArray.add(sumArray.get(i) + origArray.get(j));

        }
    }  

    --n;

    return combineTwoArrayList(n, origArray, finalSumArray);

}

You can use recursion. Basically, you should have only two for loops. (which is the code for two member combinations). When you get those sums, pass that to an Array MyArrayList2. Now for MyMethod3, you use the elements of MyArrayList2 and the original ArrayList and find sums again and pass that to MyArrayList3. For MyMethod4, you use the elements of MyArrayList3 and the original ArrayList and find sums again and pass that to MyArrayList4. For MyMethod5, yada yada yada... — Maertin
– Maertin, Commented Dec 2, 2015 at 17:33
The problem Pham Trung said will still exist. The limits for the for loop for MyMethod2 has to be i<MyArrayList.size and j<i. — Maertin
– Maertin, Commented Dec 2, 2015 at 17:39
You are correct @Maertin 2nd comment. I went back to the original code and checked. Updated the code above accordingly. Your 1st suggestion also looks good. I will an example and respond. — userDSSR
– userDSSR, Commented Dec 2, 2015 at 17:43
good, now that you got MyMethod2 working, inside the for loop, when you calculate total, pass the value of total to a new arraylist. You have to recursively call the original ArrayList against the Total arraylist for higher values of n. — Maertin
– Maertin, Commented Dec 2, 2015 at 17:47

CodeSammich · Accepted Answer · 2015-12-02 20:36:05Z

2

You are correct in wanting to do this via recursion, because now, instead of having three separate methods, you could have one method with a parameter n for n-member combinations.

public int nCombinationSum( int n, int i, ArrayList<Integer> arr, ArrayList<Integer> sumArr) {
    /* Gets n-combination sums and puts into sumArr
       Input: n consecutive element combination, current index i in arr, and output ArrayList
       Output: Gets n consecutive element combinations in arr from index i to index (i + n) and puts into sumArr
    */

    //**BASE CASE**

    //if index out of arr bounds 
    if( i + n > arr.size() )
        return 0;

    //**RECURSIVE CASE**

    else { 
        //sum of values in arr from i to (i + n)

        int currComboSum = 0; 
        for( int j = 0; j < n; j++ )
            currComboSum += arr.get(j); 

        //adding sum to next element in resultant array
        sumArr.add( currComboSum );

        return nCombinationSum( n, i + 1, arr, sumArr );
    }
}

USAGE

In your main method, you can call nCombinationSum and provide it with the kind of combination (n), starting index (in your case, 0), and arrayList (arr), and the arrayList you want to append the sums in (sumArr).

This also has the potential added benefit of allowing you to add any n-combination sum starting from a certain index. If you would like, you could add an end index as well, but this is fairly extended as it is.

EDIT: Please edit your question to reflect that you want the result to be an arrayList of sums, rather than the total sum. It is not clear right now.

Basically, what you want to do with recursion, in general, is to set a base case and a recursive case.

Your base case would be if your index is out of bounds, because you're going to call all elements from index i to i + n.

For the recursive case, use the algorithm below to account for each element in arr, then just keep returning the function with the next index value, and the function will continue running until it is out of bounds.

Algorithm

Getting sum of n-combination elements
Appending that sum into resultant array sumArr

Feel free to refer to the code above for reference.

edited Dec 2, 2015 at 20:36

answered Dec 2, 2015 at 18:05

CodeSammich

2361 gold badge3 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

userDSSR Over a year ago

Thanks @CodeSamminch, I like to code overall. The output would be an ArrayList of all the sum of (say) 3 member combination. e.g. {1,2,3,4,5} --> the output should be {6, 7, 8, 8, 9, 10, 9, 10, 11, 12}}. (5C3) The example you provided shifts the index but seems to not take care of all combinations. So, in this example it will produce {6, 9, 12} or the total sum of 27.

CodeSammich Over a year ago

Oh, I thought you wanted to get the sum of all the combinations. In that case. Will edit

CodeSammich Over a year ago

Edited. Please edit your question to make your question clearer. If I may suggest,

userDSSR Over a year ago

I just did that and added the example to the question. Thanks,

CodeSammich Over a year ago

I added a general guide to recursion + specific algorithm. Let me know if anything is not clear. (:

Maertin · Accepted Answer · 2015-12-02 17:56:23Z

1

You can use recursion. Basically, you should have only two for loops. (which is the code for two member combinations). When you compute 'total', pass each 'total' value to an ArrayList MyArrayList2. Now for MyMethod3, you use the elements of MyArrayList2 and the original ArrayList and find new 'total' values again and pass that to MyArrayList3. For MyMethod4, you use the elements of MyArrayList3 and the original ArrayList and find new 'total' values again and pass that to MyArrayList4.... ....

answered Dec 2, 2015 at 17:56

Maertin

3841 silver badge8 bronze badges

3 Comments

Maertin Over a year ago

I will in 5 hours if author hasn't figured out by then.

Ruan Mendes Over a year ago

Then this should be a comment

userDSSR Over a year ago

Thanks @Maertin. The Strategy worked. Added the code to the bottom of my question.

Collectives™ on Stack Overflow

Java Recursion on an ArrayList

2 Answers 2

USAGE

5 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

USAGE

5 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related