My accepted recursive Java solution

  • 0

    basically same as combination Sum I, but the test cases in this question have duplicates. So we need to add a line to handle that. See comment .

    public static List<List<Integer>> ans; 
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ans = new ArrayList<List<Integer>>();
        List<Integer> l0 = new ArrayList<Integer>();
        findNext(candidates, target, -1, l0);
        return ans;
    static void findNext (int[] candidates, int target, int lastIdx, List<Integer> l ){
        if (target == 0) {
        for (int i = lastIdx+1; i< candidates.length; ++i){
            if (target - candidates[i] <0) return;  
            if (i>lastIdx+1 && candidates[i-1]==candidates[i])  //handle duplicates
            List<Integer> curr = new ArrayList<Integer>(l);
            findNext(candidates, target-candidates[i], i, curr);

  • 0

    making an arraylist every time in recursion?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.