Solving Combination Sum

To see the question, click here.

Naive Approach

The idea is to use the concept of backtracking. Initialize a result list to store all valid combinations and a temporary list temp to store the current combination being explored. Assume a recursive function f is called to generate combinations recursively. This function takes several parameters: the current index i, the input array candidates, the target sum, the result list result, the temporary list temp, the current sum currSum, and the length of the candidates array n. The function then explores two possibilities at each step, including the current element candidates[i] in the combination or excluding it. When the element is included, it is added to temp, and currSum is updated accordingly. The function is called recursively with the same index i to allow repeated use of the same element. When the element is excluded, it is removed from temp, and currSum is decremented accordingly. The function is called recursively with the next index i + 1 to explore the next element. This approach ensures that every possible combination that sums to the target is generated by exploring each element's inclusion or exclusion. Backtracking is used to remove the last added element from temp before exploring the exclusion path, ensuring all combinations are considered. This method guarantees that all valid combinations are efficiently generated and stored in the result list. The base case of the recursion occurs when the index i equals n or the currSum exceeds the target.

// TC: O(2^n)
// SC: O(n)

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

class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        int n = candidates.length;
        f(0, candidates, target, result, temp, 0, n);
        return result;
    }

    public void f(int i, int[] candidates, int target, List<List<Integer>> result, List<Integer> temp, int currSum,
            int n) {
        if (i == n || currSum > target) {
            return;
        }

        if (currSum == target) {
            result.add(new ArrayList<>(temp));
            return;
        }

        // include
        currSum += candidates[i];
        temp.add(candidates[i]);
        f(i, candidates, target, result, temp, currSum, n);

        // exclude
        currSum -= candidates[i];
        temp.remove(temp.size() - 1);
        f(i + 1, candidates, target, result, temp, currSum, n);
    }

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

Performance

The time complexity of the combinationSum method is O(2^n) because we have two choices for each element in the candidate's array: either include it in the combination or exclude it. This results in a binary tree of height n. As a result, the total number of combinations that can be formed is 2^n. The space complexity is O(n) because we are using a temporary list to store the current combination, and the maximum size of this list is equal to the number of elements in the array.

Refined Approach

Start by sorting the array. This allows us to break early from the recursion when the current sum exceeds the target, as all further elements will only make the sum larger. Instead of passing currSum around, we can calculate the sum directly in the recursive call by including or excluding the current candidate. It's important to note that the fundamental time complexity might not drastically change due to the nature of the problem.

// TC: O(2^n)
// SC: O(n)

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

public class CombinationSum {

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

    public void f(int[] candidates, int target, List<List<Integer>> result, List<Integer> temp, int start) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
            temp.add(candidates[i]);
            f(candidates, target - candidates[i], result, temp, i); // not i + 1 because we can reuse same elements
            temp.remove(temp.size() - 1); // remove the last element for backtracking
        }
    }

    public static void main(String[] args) {
        CombinationSum solution = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = solution.combinationSum(candidates, target);
        System.out.println(result);
    }
}

Performance

The time complexity of the combinationSum method is O(2^n) because we have two choices for each element in the candidate's array: either include it in the combination or exclude it. This results in a binary tree of height n. As a result, the total number of combinations that can be formed is 2^n. The space complexity is O(n) because the recursion stack can reach a depth of n as we explore all possible combinations of elements in the array. While the worst-case time complexity remains exponential due to the nature of the problem, these optimizations can significantly improve performance in practice by reducing the number of paths explored.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.