Backtracking Java solution beats 84% of solutions (19ms). With comments.


  • 0
    L
    List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list = new ArrayList<>();
        combinationSum(candidates, 0, target, list);
    
        return result;
    }
    
    public void combinationSum(int[] candidates, int startIndex, int target, List<Integer> currentList) {
        // if the target is less than zero, we went too far 
        if (target < 0) return;
    
        // great, we found a solution
        if (target == 0) { 
            result.add(currentList);
            return;
        }
    
        for (int i = startIndex; i < candidates.length; i++) {
            int num = candidates[i];
            if (num <= target) {
                // create a new list for this call stack and copy the old elements
                List<Integer> newList = new ArrayList<>(currentList);
                newList.add(num); // add this new element to the list
    
                // now backtrack with new parameters updated. the key here is that
                // we will start at i in the next iteration in order to avoid duplicates
                combinationSum(candidates, i, target - num, newList);
            }
        }
    }

Log in to reply
 

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