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>();
        Arrays.sort(candidates);
        findNext(candidates, target, -1, l0);
        return ans;
    }
    
    static void findNext (int[] candidates, int target, int lastIdx, List<Integer> l ){
        if (target == 0) {
            ans.add(l);
            return;
        }
    
        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
                continue;
            List<Integer> curr = new ArrayList<Integer>(l);
            curr.add(candidates[i]);
            findNext(candidates, target-candidates[i], i, curr);
        }
    }

  • 0
    M

    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.