Why is my innerList is not adding in the answers?

Question

This question is of combination sum. I tried it through recursion and backtracking but my output is becoming an empty list of lists every time.

public class CombinationSum {

    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        System.out.println(combinationSum(candidates,8));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> currComb = new ArrayList<>();
        getResult(candidates,target,currComb,0,0,ans);
        return ans;
    }

    public static void getResult(int[] candidates,int target, List<Integer> currComb, int currSum, int currIndex,List<List<Integer>> ans) {
        if (currSum > target) {
            return;
        }
        if (currSum == target) {
            ans.add(currComb);
            return;
        }

        for (int i = 0; i < candidates.length ; i++) {
            currComb.add(candidates[i]);
            currSum += candidates[i];
            getResult(candidates, target, currComb, currSum, i, ans);
            currComb.remove(currComb.size() -1);
            currSum -= candidates[i];
        }
    }
}

Answer 1

There are some things that are wrong with this code of yours.

ans.add(currComb);

This would always give you the wrong result even if your code was right. List is a reference type in Java so you should always add a new instance of list in your answer. For example

ans.add(new ArrayList(currComb));

You are passing in currIndex but you are not using it. You probably need to call your recursive function twice to simulate whether or not you are adding it to your list.

I solved this question last night on LeetCode. This was my code and it worked for me.

class Solution {
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList();
        if(nums == null || nums.length == 0) {
            return res;
        }
        dfs(res, nums, 0,target, new ArrayList());
        return res;
    }
    public void dfs(List<List<Integer>> res, int[] nums, int i, int target, List<Integer> temp) {
        if(target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        if(target < 0 || i >= nums.length) {
            return;
        }
        
        temp.add(nums[i]);
        dfs(res, nums, i, target - nums[i], temp);
        temp.remove(temp.size() - 1);
        dfs(res, nums, i+1, target, temp);
    }
}