Combination Sum - LeetCode Solution in Java

1. Introduction

The "Combination Sum" problem focuses on finding all unique combinations of numbers from a given array that sum up to a target number. This problem tests knowledge of backtracking and recursion in algorithms.

2. Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

3. Solution Steps

1. Use a backtracking approach to solve the problem.

2. Sort the candidates array to handle duplicates and optimize.

3. Create a recursive function to explore each possibility.

4. Add candidates to the current combination if they don't exceed the target.

5. Recurse with the updated current combination and target.

6. Once the target is reached, add the combination to the result.

4. Solution in Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates); // Sort candidates
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> tempCombination, int[] candidates, int remain, int start) {
    if (remain < 0) return; // if combination exceeds the target, stop
    else if (remain == 0) result.add(new ArrayList<>(tempCombination)); // combination equals target, add to result
    else {
        for (int i = start; i < candidates.length; i++) {
            tempCombination.add(candidates[i]); // add the number to the current combination
            backtrack(result, tempCombination, candidates, remain - candidates[i], i); // not i + 1 because we can reuse same elements
            tempCombination.remove(tempCombination.size() - 1); // backtrack
        }
    }
}

This solution employs a backtracking approach, systematically exploring all potential combinations, adding candidates to the current combination, and backtracking when necessary to explore other possibilities.

Explanation:

1. The backtrack method is used to explore each possibility.

2. Candidates are sorted to optimize the process and handle duplicates.

3. If the current combination exceeds the target, the recursion stops (remain < 0).

4. If the combination equals the target, it is added to result.

5. The algorithm explores each number, adds it to the current combination, and recurses, reducing the target by the added number.

6. It allows the same number to be reused by passing i instead of i + 1 to the next recursion.

7. Backtracking is done by removing the last element added to the combination.