Combination Sum – 39. LeetCode

Imagine you’re given a list of numbers and a target value. You need to figure out all the unique ways to combine these numbers so their total equals the target. You can use any number as many times as you want, but the order of numbers in the combination does not matter.

Brute Force Approach

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // Initialize a list to hold the combinations
        List<List<Integer>> result = new ArrayList<>();
        // Add an initial empty combination
        result.add(new ArrayList<>());

        for (int candidate : candidates) {
            List<List<Integer>> newCombinations = new ArrayList<>();

            for (List<Integer> combination : result) {
                int sum = sum(combination);
                while (sum + candidate <= target) {
                    List<Integer> newCombination = new ArrayList<>(combination);
                    newCombination.add(candidate);
                    newCombinations.add(newCombination);
                    sum += candidate; // Simulate adding more of the same candidate
                }
            }
            result.addAll(newCombinations);
        }

        // Filter out combinations that don't sum to the target
        List<List<Integer>> finalResult = new ArrayList<>();
        for (List<Integer> combination : result) {
            if (sum(combination) == target) {
                finalResult.add(combination);
            }
        }

        return finalResult;
    }

    // Helper function to calculate the sum of a list
    private int sum(List<Integer> combination) {
        int total = 0;
        for (int num : combination) {
            total += num;
        }
        return total;
    }
}

• For each number in candidates, try adding it to existing combination in result.
• For each existing combination, simulate adding the current candidate multiple times until the sum exceeds target.
• After building all possible combinations, filter out invalid ones where the sum does not equal the target.

Optimal Approach

Algorithm & Data Structure

• Algorithm: Backtracking with Pruning

• Data Structure: Recursive function with a dynamic list (ArrayList) to build combinations.

Instead of blindly exploring all paths, use backtracking to make intelligent decisions:

1. Only add valid numbers that don’t exceed the remaining target.

2. Prune unnecessary branches early, avoiding wasted computations.

3. Build combinations incrementally, and backtrack when a solution is found or invalid paths are detected.

Backtracking is a general algorithmic pattern for solving combinatorial problems like permutations, combinations, and subsets.

Steps of Algorithm:

1. Initialize an empty result list to store valid combinations.

2. Start backtracking from the first number, trying each number incrementally.

3. If the target becomes 0, store the current combination.

4. If the target becomes negative, backtrack (terminate the current path).

5. Use a recursive helper function to explore combinations.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) { // Base case: valid combination
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0) return; // Base case: exceeded target

        for (int i = start; i < candidates.length; i++) {
            current.add(candidates[i]); // Choose current number
            backtrack(candidates, target - candidates[i], i, current, result); // Explore
            current.remove(current.size() - 1); // Undo choice (backtrack)
        }
    }
}

Line-By-Line Explanation

Step 1: Initialize state and backtracking

List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;

• result will store all valid combinations.
• The backtrack method is called to recursively explore all possible ways to combine numbers from candidates to reach the target.
• This sets up the process to build combinations using backtracking, initializing the required variables and kicking off the recursive function.

Step 2: Base Cases

if (target == 0) { // Base case: valid combination
    result.add(new ArrayList<>(current));
    return;
}
if (target < 0) return; // Base case: exceeded target

• If target == 0, the current combination (current) is valid, so it is added to the result.
• If target < 0, the current combination cannot be valid, so step further exploration.
• These are the stopping conditions for the recursion.

Step 3: Explore Combinations

for (int i = start; i < candidates.length; i++) {
    current.add(candidates[i]); // Choose current number
    backtrack(candidates, target - candidates[i], i, current, result); // Explore
    current.remove(current.size() - 1); // Undo choice (backtrack)
}

• The loop iterates through all candidates starting from the start index.

• For each candidate:
  • Add it to the current combination.
  • Recursively call backtrack with the updated target.
  • Remove the candidate from the combination to explore other possibilities.
• This step builds the combinations incrementally, exploring all valid paths and backtracking when a path fails.
• The start index ensures no duplicate combinations are generated by only considering candidates at or after the current position.

Why This Code Works

This algorithm solves the problem by systematically exploring all combinations of numbers that add up to the target, ensuring no duplicates by managing the start index. The recursive backtracking approach ensures every possible valid combination is considered while pruning invalid paths early.

This methodology is efficient, clear, and adaptable, making it one of the best solutions for Combination Sum on LeetCode.