Combination Sum - Java Solution

1. Introduction

This post explores the "Combination Sum" problem, a classic challenge often encountered in algorithm design and coding interviews. The problem involves finding all unique combinations of a set of numbers that add up to a given target sum, with the twist that each number can be used multiple times.

Problem

Given an array of distinct integers 'candidates' and a target integer 'target', we need to return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times, and combinations are considered unique based on the frequency of at least one of the chosen numbers.

2. Solution Steps

1. Sort the 'candidates' array to facilitate the combination process.

2. Use a backtracking approach to explore all possible combinations.

3. For each number in the candidates array, recursively try to build a combination that adds up to the target.

4. If the sum of the current combination exceeds the target, backtrack.

5. If the sum equals the target, add the current combination to the result list.

6. Return the list of all unique combinations.

3. Code Program

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

public class CombinationSum {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        System.out.println(combinationSum(candidates, target)); // Test the function
    }

    // Function to find all unique combinations that sum up to the target
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // Sort the candidates
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    // Helper function for backtracking
    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain < 0) return; // If the remainder is negative, no solution
        else if (remain == 0) result.add(new ArrayList<>(tempList)); // Found a combination
        else {
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]); // Choose the number
                backtrack(result, tempList, candidates, remain - candidates[i], i); // Explore further with reduced remainder
                tempList.remove(tempList.size() - 1); // Backtrack
            }
        }
    }
}

Output:

[[2, 2, 3], [7]]

Explanation:

1. combinationSum: This function initializes the process to find combinations. It sorts the candidates array and calls the backtrack function.

2. backtrack: A recursive helper function that explores each candidate. It tries to build a valid combination by adding the current candidate and reducing the target remainder.

3. The function adds a candidate to the current list (tempList), recursively calls itself with a reduced target (remain - candidates[i]), and then removes the last added candidate to backtrack.

4. When the remainder becomes 0, it means a valid combination is found, which is then added to the result list.

5. If the remainder becomes negative, the function backtracks as the current path does not lead to a valid combination.

6. The result is a list of all unique combinations of candidates that sum up to the target.