Very easy-understanding Java solution with recursion

  • 0

    Main idea:

    • Iteratively choose the elements in the given candidates.
    • Recursively construct the result with backtracking.

    AC code:

    public class Solution {
      List<List<Integer>> ret;
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<List<Integer>>();
        int len = candidates.length;
        List<Integer> tmp = new ArrayList<Integer>();
        List<Integer> rem = new ArrayList<Integer>();
        for(int i=0;i<len;i++) rem.add(candidates[i]);
        return ret;
      private void func(List<Integer> tmp, List<Integer> rem, int target){
          return ;
          for(int i=0;i<rem.size();i++){
            List<Integer> tmp1 = new ArrayList<Integer>(tmp);
            // Stop for useless combination to save time
            if(getSum(tmp1)>target) break;
            List<Integer> rem1 = new ArrayList<Integer>();
            for(int j=i;j<rem.size();j++)
            func(tmp1, rem1, target);
      private int getSum(List<Integer> tmp){
        int sum=0;
        for(int x:tmp)
        return sum;

    While, can anyone told me why my solution is slower than the average? (The pervasive solution is to deduct the target, while mine is to add up to the target. I think the idea and process is the same...). Thanks for you advice~

Log in to reply

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