The LeetCode problem “Combination Sum” asks us to find all unique combinations of numbers from a given list (array) that sum up to a specified target. Each number in the array can be used multiple times in the combination. For example, given the array [2, 3, 6, 7] and a target of 7, the valid combinations are [7] and [2, 2, 3].
Algorithm and Data Structure Choice
Chosen Algorithm: Backtracking
Backtracking is commonly used in combinatorial problems where valid arrangements or selections are needed (e.g., combinations, permutations, subsets). It allows systematic exploration while meeting constraints, and it’s especially useful when we need to generate multiple possible solutions.
1. Combination Generation with Repetition Allowed: The task requires generating combinations where numbers can repeat, making backtracking effective.
2. Decision Tree Exploration: The problem can be visualized as a tree where each level represents a decision (whether to add a specific number to the current combination), and backtracking allows us to explore each path to the target.
3. Target Sum Constraints: The problem has a target that needs to be met exactly, so backtracking can efficiently prune paths that exceed the target, saving unnecessary computation.
The backtracking algorithm is a systematic way of exploring all possible combinations to reach a target sum by incrementally building valid combinations.
• Time Complexity: O(2^n) in the worst case, where n is the number of candidates, as we explore multiple combinations recursively.
• Space Complexity: O(n) due to the recursive call stack for each element being added to the combination.
High-Level Algorithm Steps
1. Define a Backtracking Function: This function will track the current combination, the remaining target, and the start index to ensure no duplicate combinations.
2. Base Case: If the remaining target is zero, add the current combination to the result.
3. Loop Through Candidates:
• If a candidate does not exceed the remaining target, add it to the current combination.
• Recursively call the backtracking function with the updated remaining target.
• Remove the last element from the combination to backtrack and explore the next candidate.
4. Return Results: After exploring all valid combinations, return the results.
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>(); // To store all valid combinations
backtrack(result, new ArrayList<>(), candidates, target, 0); // Start backtracking
return result; // Return the final result
}
private void backtrack(List<List<Integer>> result, List<Integer> combination, int[] candidates, int remaining, int start) {
if (remaining == 0) { // Found a valid combination
result.add(new ArrayList<>(combination)); // Add it to the results
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) continue; // Skip if the candidate exceeds remaining
combination.add(candidates[i]); // Choose the candidate
backtrack(result, combination, candidates, remaining - candidates[i], i); // Recur with the updated remaining and same index
combination.remove(combination.size() - 1); // Backtrack: remove the last added candidate
}
}
}Line-By-Line Explanation
- Result Storage
List<List<Integer>> result = new ArrayList<>();
• A list to hold all valid combinations found during the backtracking process.
2. Starting Backtracking
backtrack(result, new ArrayList<>(), candidates, target, 0);
• Call the backtracking helper function with an empty combination, the target, and a starting index of 0.
3. Backtracking Method
private void backtrack(List<List<Integer>> result, List<Integer> combination, int[] candidates, int remaining, int start) {
• This method handles the core logic of exploring combinations. Parameters include the result list, the current combination being built, the candidates array, the remaining target, and the starting index.
4. Base Case
if (remaining == 0) {
result.add(new ArrayList<>(combination));
return;
}5. Loop Through Candidates
for (int i = start; i < candidates.length; i++) {- Iterate through the candidates starting from the specified index to avoid duplicates in the results.
6. Check Remaining Target
if (candidates[i] > remaining) continue;
• If the current candidate exceeds the remaining target, skip it. This prevents the sum from exceeding the target unnecessarily.
7. Add Candiate
combination.add(candidates[i]);
• Include the current candidate in the ongoing combination.
8. Recursive Call
backtrack(result, combination, candidates, remaining - candidates[i], i);
• Recursively call backtrack with the updated remaining target (reduced by the current candidate) and the same index i to allow the candidate to be reused.
9 Backtrack
combination.remove(combination.size() - 1);
• Remove the last candidate added to backtrack and explore other combinations with different candidates.
10. Return Result
return result;Why This Code Was Coded This Way
Why This Code Was Coded This Way
• Clarity and Structure: Separating the main function and the backtracking helper keeps the code clean and easy to understand.
• Efficiency: Pruning paths that exceed the target avoids unnecessary computations, improving efficiency.
• Simplicity: The recursive structure of backtracking is straightforward and allows the code to handle all possible combinations systematically.
Overall, this backtracking approach effectively finds all valid combinations that meet the target sum while minimizing redundant calculations.
