Java Recursion Pass by Reference in ArrayList

Question

I am working on a problem to find which all combinations of integer in a given list can sum up to a given number.

public class SumProblem {

/*
 * Input 2-2-3-7
 * Output 2+2+3 and 7
 */

public static ArrayList<ArrayList<Integer>>  find(ArrayList<Integer> input, int requiredSum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    find(result, requiredSum, 0, new ArrayList<>(), 0, input);
    return result;
}

public static void find(ArrayList<ArrayList<Integer>> result , int requiredSum , int currentSum,  ArrayList<Integer> partialResult, int i, ArrayList<Integer> input) {

    if (currentSum == requiredSum ) {
        ArrayList<Integer> temp = new ArrayList<>();
        temp = (ArrayList<Integer>) partialResult.clone();
        result.add(temp);
        return;
    }

    if (i >= input.size()) {
        return;
    }
    find(result, requiredSum, currentSum , partialResult, i +1, input );
    partialResult.add(input.get(i));
    find(result, requiredSum, currentSum + input.get(i) , partialResult, i +1, input );
}

public static void main(String[] args) {

    ArrayList<Integer> input = new ArrayList<>();
    input.add(2);
    input.add(1);
    input.add(3);
    ArrayList<ArrayList<Integer>>  output = find(input, 3);
    System.out.println(output.toString());
}

}

I have written code below. I am facing one problem. In the below line of code, it is adding up all the numbers i traverse even if i create new ArrayList object and assign it to partialResult.

partialResult.add(input.get(i));

Could anyone suggest the solution ?

Without any code in the method, it's difficult to understand what problem you have, and what you're doing wrong to even have that problem. --- E.g. does "start afresh" mean partialResult.clear()? Does "transfer partialResult into results" mean results.add(new ArrayList<>(partialResult))? If so, what is your actual problem? If not so, then what? — Andreas
– Andreas, Commented Jul 1, 2018 at 6:44
@Manish not enough code. Show the part calling your "find" method — mangusta
– mangusta, Commented Jul 1, 2018 at 7:40
Do you mean something like find (results, new ArrayList<>(), i) ? — c0der
– c0der, Commented Jul 1, 2018 at 7:40

David Conrad · Accepted Answer · 2018-07-01 08:46:08Z

You have two recursive calls in this dynamic programming solution to the problem. One is supposed to not include the current value in the result, the other does.

You need to make a defensive copy of partialResult, otherwise both recursive calls are going to have a reference to the same list. A list is a mutable object. If both calls get a reference to the same list object, then when you add something to it anywhere, both of them will see the modified list.

The easiest way to make a defensive copy of a list is just to write:

new ArrayList<>(partialResult)

Here is a working version of the program:

import java.util.*;

public class SumProblem {
    public static List<List<Integer>> find(List<Integer> input, int requiredSum) {
        List<List<Integer>> result = new ArrayList<>();
        find(result, requiredSum, 0, new ArrayList<>(), 0, input);
        return result;
    }

    public static void find(List<List<Integer>> result, int requiredSum, int currentSum,
            List<Integer> partialResult, int i, List<Integer> input) {
        if (currentSum == requiredSum) {
            result.add(new ArrayList<>(partialResult)); // add a copy of the list
            return;
        }

        if (i >= input.size()) {
            return;
        }
        // make defensive copies in the recursive calls
        find(result, requiredSum, currentSum, new ArrayList<>(partialResult), i + 1, input);
        partialResult.add(input.get(i));
        find(result, requiredSum, currentSum + input.get(i), new ArrayList<>(partialResult), i + 1, input);
    }

    public static void main(String[] args) {
        List<Integer> input = List.of(2, 8, 2, 3, 4);
        List<List<Integer>> output = find(input, 7);
        System.out.println(output);
    }
}

Output:

[[3, 4], [2, 2, 3]]

I've made a few other changes:

Use List<Integer> and List<List<Integer>> as the types (code to the interface)
Use List.of() to create the input list (added in Java 9)
Don't call toString() on objects passed to println — it's unneeded

Collectives™ on Stack Overflow

Java Recursion Pass by Reference in ArrayList

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related