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) {
        Arrays.sort(candidates);
        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]);
        func(tmp,rem,target);    
        return ret;
      }
      private void func(List<Integer> tmp, List<Integer> rem, int target){
        if(getSum(tmp)==target){
          ret.add(tmp);
          return ;
        }
        if(getSum(tmp)<target){
          for(int i=0;i<rem.size();i++){
            List<Integer> tmp1 = new ArrayList<Integer>(tmp);
            tmp1.add(rem.get((int)i));
            // 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++)
              rem1.add(rem.get((int)j));
            func(tmp1, rem1, target);
          }
        }
      }
      private int getSum(List<Integer> tmp){
        int sum=0;
        for(int x:tmp)
          sum+=x;
        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.