Simple java solution


  • 5
    H
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, 0, target, new ArrayList<Integer>());
        return res;
    }
    
    private void helper(int[] can, int start, int target,List<Integer> each) {
        for (int i = start; i < can.length; i++) {
            List<Integer> temp = new ArrayList<>(each);
            if (can[i] == target) {
                temp.add(can[i]);
                res.add(temp);
                break;
            } else if (can[i] < target) {
                temp.add(can[i]);
                helper(can, i, target - can[i], new ArrayList<>(temp));
            } else {break;}
        }
        return;
    }

  • 1
    C

    Nice Solution! I solved this problem with the same idea. However, instead of using res as a field, i made it as a local variable in my program:

    • if candidates[i] == target, add it and return;

    • if candidates[i] > target, it means we can break this loop since no combination starting from this element could sum up to target;

    • if candidates[i] < target, we can recursively find the solution starting from the same element but different target number (which is current target - candidates[i]).

       public class Solution {
           public List<List<Integer>> combinationSum(int[] candidates, int target) {
               List<List<Integer>> result = new ArrayList<>();
               if (candidates == null || candidates.length == 0) return result;
               Arrays.sort(candidates);
               return combinationSum(candidates, target, 0);
           }
       
       private List<List<Integer>> combinationSum(int[] candidates, int target, int start) {
           List<List<Integer>> result = new ArrayList<>();
           for (int i = start; i < candidates.length; i++) {
               if (candidates[i] == target) {
                   List<Integer> temp = new ArrayList<>();
                   temp.add(candidates[i]);
                   result.add(temp);
                   return result;
               }
               if (candidates[i] > target) return result;
               List<List<Integer>> next = combinationSum(candidates, target - candidates[i], i);
               if (next.size() == 0) continue;
               for (List<Integer> list : next) list.add(0, candidates[i]);
               result.addAll(next);
           }
           return result;
       }
      

      }


  • 1
    Z

    Change this line :

    helper(can, i, target - can[i], new ArrayList<>(temp));
    

    to:

    helper(can, i, target - can[i], temp);
    

    The performance will be much better.


  • 0
    C

    Your answer is not correct if the input is [2,2,3,6,7]. it's strange that it can past the online test.


  • 0
    T

    And if you change the loop to (i.e. get rid of temp copy):

        if (can[i] == target) {
            each.add(can[i]);
            res.add(new ArrayList(each));
            each.remove(each.size()-1);
            break;
        } else if (can[i] < target) {
            each.add(can[i]);
            helper(can, i, target - can[i], each);
            each.remove(each.size()-1);
        } else {break;}
    

    You should have even better performance.


  • 0
    T

    @coco_sally The problem statement says: "Given a set of candidate numbers".

    As StefanPochmann told me in a similar occasion: GIGO.


Log in to reply
 

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