Combination Sum medium

Problem Statement

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.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It's guaranteed that the number of unique combinations is less than 150.

Example 1

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates. 2 + 2 + 3 = 7. Another combination is 7.

Example 2

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Explanation: 2, 3 and 5 are candidates. 2 + 2 + 2 + 2 = 8. 2 + 3 + 3 = 8. 3 + 5 = 8.

Steps

1. Sort the candidates: Sorting allows for early termination of branches in the search space when the current sum exceeds the target.
2. Backtracking: Use a recursive backtracking function to explore all possible combinations.
3. Base Cases:
   • If the current sum equals the target, add a copy of the current combination to the result list.
   • If the current sum exceeds the target, or if we have reached the end of the candidates array, return.
4. Recursive Step: For each candidate, recursively call the function with:
   • The same target (since we can reuse candidates)
   • The current sum updated by adding the candidate
   • An updated combination list including the current candidate
5. Return the result: After exploring all possibilities, return the list of combinations.

Explanation

The solution employs a backtracking algorithm, which systematically explores all possible combinations. Sorting the candidates helps to optimize the search by pruning branches that are guaranteed to exceed the target. The base cases handle situations where a combination is found or the search should be stopped. The recursive step explores adding each candidate to the current combination, effectively building up all valid combinations.

Code

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

public class CombinationSum {

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

    private void backtrack(int[] candidates, int target, int start, List<Integer> combination, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(combination)); // Add a copy to avoid modification
            return;
        }
        if (target < 0 || start >= candidates.length) {
            return; // Base cases
        }

        // Include the current candidate
        combination.add(candidates[start]);
        backtrack(candidates, target - candidates[start], start, combination, result); // Explore with the same candidate

        // Exclude the current candidate
        combination.remove(combination.size() - 1);
        backtrack(candidates, target, start + 1, combination, result); // Explore with the next candidate
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        int[] candidates1 = {2, 3, 6, 7};
        int target1 = 7;
        System.out.println(cs.combinationSum(candidates1, target1)); // Output: [[2, 2, 3], [7]]

        int[] candidates2 = {2, 3, 5};
        int target2 = 8;
        System.out.println(cs.combinationSum(candidates2, target2)); // Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
    }
}

Complexity

• Time Complexity: O(2^N * K), where N is the number of candidates, and K is the average length of a combination. The worst-case scenario is exploring all possible subsets.
• Space Complexity: O(K * M), where K is the average length of a combination and M is the number of combinations in the result. The space is primarily used for the recursion stack and storing the result list. The space used by the result list depends on the number of combinations found.