Arraylist is not getting updated in recursion correctly

Question

Below is my function which gives all the possibilities that the elements in a given array sums up to a specific target. I am able to print the lists, however the result list is not getting updated.

public List<List<Integer>> helper(List<List<Integer>> res, int[] c, int l, int h, int target, List<Integer> temp){
        if(target == 0){
            res.add(temp);
            System.out.println(temp);
            return res;
        }
        if(target < c[l]){
            return res; 
        }
        for(int i = l; i <=h; i++){
            temp.add(c[i]);
            res = helper(res, c,i,h,target-c[i], temp);
            temp.remove(temp.size()-1);
        }
        return res;
    }

res is arraylist of empty arraylists in the end, but the 5th line prints the temp arraylist correctly.

The function is called as below.

List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
res = helper(res,candidates, 0, candidates.length-1, target, temp);

Example: Given array = [1,2,3], target = 6

stdout:

[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 2]
[1, 2, 3]
[2, 2, 2]
[3, 3]

res is [[],[],[],[],[],[],[]]

what's your input and what results did your debugging show? – f1sh Feb 22 '19 at 18:26 — f1sh, Feb 22 '19 at 18:26
Updated with the inputs and results – Gurupad Hegde Feb 22 '19 at 18:33 — Gurupad Hegde, Feb 22 '19 at 18:33

Jainik · Answer 1 · 2019-02-22T19:28:07.937

This is standard pass by reference against pass by value issue.

You are adding a reference of a temp to the res object so whenever value of temp changed (which does within for loop in your program), it changes value of an instance in res as well so at the end when all elements has been removed from the temp, list becomes empty and then it changes all value within res to an empty list.

Change your helper method first if condition as below and it should work:

if(target == 0){
  ArrayList<Integer> copy = new ArrayList<>(temp);
  res.add(copy);
  return res;
}

Explanation

Instead of adding a reference of a temp to res, we are creating a simple copy of temp and then add it to res.

This prevents value being overwritten with the new object value.

Vikas · Answer 2 · 2019-02-22T20:38:24.300

1

Every time you are adding temp to res. So everytime you are adding same temp reference to res list. In the end temp will be an empty list so all the values in res will be empty as they are pointing to same temp reference. If you pass new list for temp, you can fix this problem.

public static List<List<Integer>> helper(List<List<Integer>> res, int[] c, int l, int h, int target, List<Integer> temp){
        if(target == 0){
            res.add(temp);
            System.out.println(temp);
            return res;
        }
        if(target < c[l]){
            return res; 
        }
        for(int i = l; i <=h; i++){
            temp.add(c[i]);
            res = helper(res, c,i,h,target-c[i], new ArrayList<Integer>(temp));
            temp.remove(temp.size()-1);
        }
        return res;
    }

edited Feb 22 '19 at 20:38

answered Feb 22 '19 at 19:43

Vikas

6,868
4
27
41

what is called a shallow copy? adding a reference to a list sure not - https://stackoverflow.com/q/184710/85421 – user85421 Feb 22 '19 at 20:02
Actually its not a shallow copy. Its just holding the reference of temp. Check updated answer. – Vikas Feb 22 '19 at 20:38
@CarlosHeuberger I was considering some other case which was not valid. So I corrected the answer. – Vikas Feb 22 '19 at 21:12

Arraylist is not getting updated in recursion correctly

2 Answers2