I ran into an issue while getting value for a List<List<Integer>> called res. It's a recursive call and that call is supposed to fill this "res", however when the recursive function is called by another function and that function is returning an empty list. But when I do log it, I can see the values. Here's the code:
class Solution {
public List<List<Integer>> combinationSum(int[] arr, int k) {
// given an arr and a sum k, find all the subsequences that sum upto k
// we can use backtracking here as we need all the options
// there are 2 choices for every element:
// either we can take it in the subres or discard it
// if we take it once, we can take it n times till the target is reached
Arrays.sort(arr);
List<List<Integer>> res = new ArrayList<>();
List<Integer> subRes = new ArrayList<>();
combinationSum(0, arr, k, 0, res, subRes);
return res;
}
public void combinationSum(int i, int[] arr, int k, int sum,
List<List<Integer>> res,
List<Integer> subRes){
if(sum == k) {
if(!res.contains(subRes)) res.add(subRes);
System.out.println("res = " + res);
return;
}
if(i == arr.length || sum > k) return;
subRes.add(arr[i]);
sum += arr[i];
combinationSum(i, arr, k, sum, res, subRes);
subRes.remove(new Integer(arr[i]));
sum -= arr[i];
combinationSum(i + 1, arr, k, sum, res, subRes);
}
}
I'm stuck badly on this, Thanks in advance.
The mutations you make to subRes in the recursion is affecting what you see in res. Before adding subRes into res, make a new copy of it.
if(!res.contains(subRes)) {
res.add(new ArrayList<>(subRes));
}
In your code, correct list (subRes) is added to res, but you mutate/modify subRes by removing elements sometime later when the recursive call returns.