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
– f1sh

2019-02-22 18:26:44 +00:00
Commented Feb 22, 2019 at 18:26 — f1sh
– f1sh, Commented Feb 22, 2019 at 18:26
Updated with the inputs and results

Gurupad Hegde
– Gurupad Hegde

2019-02-22 18:33:53 +00:00
Commented Feb 22, 2019 at 18:33 — Gurupad Hegde
– Gurupad Hegde, Commented Feb 22, 2019 at 18:33

Jainik · Accepted Answer · 2019-02-22 19:28:07Z

4

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.

edited Feb 22, 2019 at 19:28

answered Feb 22, 2019 at 19:20

Jainik

2,4721 gold badge22 silver badges27 bronze badges

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

Comments

Vikas · Accepted Answer · 2019-02-22 20:38:24Z

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, 2019 at 20:38

answered Feb 22, 2019 at 19:43

Vikas

7,2214 gold badges30 silver badges46 bronze badges

3 Comments

user85421 Over a year ago

what is called a shallow copy? adding a reference to a list sure not - stackoverflow.com/q/184710/85421

Vikas Over a year ago

Actually its not a shallow copy. Its just holding the reference of temp. Check updated answer.

Vikas Over a year ago

@CarlosHeuberger I was considering some other case which was not valid. So I corrected the answer.

Collectives™ on Stack Overflow

Arraylist is not getting updated in recursion correctly

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related