CODEWITHSUNDEEP
javarecursion
Gurupad Hegde
Gurupad Hegde

Reputation: 85

Arraylist is not getting updated in recursion correctly

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 [[],[],[],[],[],[],[]]

Upvotes: 5

Views: 948

Answers (2)

Vikas
Vikas

Reputation: 7175

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;
    }

enter image description here

Upvotes: 1

Jainik
Jainik

Reputation: 2452

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.

Upvotes: 4

Related Questions