Short but slow JAVA AC solution. Any improvement ideas? Thx!


  • 0
    L

    My code below. Consider the search space as a large tree, where each node's children are the candidates equal or larger than itself. The helper function traverses the tree using BFS.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        
        Arrays.sort(candidates);
        helper(new ArrayList<Integer>(), res, target, candidates, 0);
        
        return res;
    }
    
    private void helper(List<Integer> currPath, List<List<Integer>> res, int target, int[] candidates, int startInd) {
        if (startInd >= candidates.length) {
            return;
        }
        while (target > 0) {
            helper(new ArrayList<>(currPath), res, target, candidates, startInd + 1);
            target -= candidates[startInd];
            currPath.add(candidates[startInd]);
        }
        if (target < 0) {
            return;// invalid.
        } else {
            // target == 0
            res.add(currPath);
            return;
        }
    }
    

    The code is AC, but it takes 22ms. Any improvement ideas? Thanks!


Log in to reply
 

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