39. Combination Sum


Problem Description

This problem presents us with a challenge: given a list of distinct integers called candidates and a target integer called target, we need to find all unique combinations of these candidates that add up to the target. The crucial part to note is that each number from candidates can be used repeatedly––an unlimited number of times.

A combination is considered unique if the count of at least one of the numbers in it differs from that in any other combination. The result can be in any order and doesn't have to be sorted.

To narrow down the possibilities, the problem assures us that the total number of unique combinations won't exceed 150 for the input provided.

Intuition

The intuition behind solving this problem involves employing a classic backtracking approach called Depth-First Search (DFS). The idea is to explore all possible combinations that can add up to the target by building them incrementally and backtracking whenever we either achieve the target sum or exceed it.

  1. Sorting Candidates: We start by sorting the list of candidates. While not necessary for the solution's correctness, this step can optimize the process by allowing us to stop early when the current candidate exceeds the remaining target sum.

  2. DFS Function: We define a recursive function, dfs, to explore different combinations. The function takes two parameters: i representing the index of the current candidate and s for the remaining sum we need to reach the target. Within this function, we have two base cases:

    • If s becomes 0, we've found a valid combination and add a copy of the current combination to the list of answers.
    • If i is out of bounds or the current candidate exceeds s, we cannot make a combination with the present choices and need to backtrack.
  3. Exploring Candidates: At each step, we have two choices:

    • Skip the current candidate and proceed to the next one using dfs(i + 1, s).
    • Include the current candidate in the current combination, adjust the remaining sum s by subtracting the candidate's value, and stay at the current index assuming we can pick it again with dfs(i, s - candidates[i]). We also need to add the included candidate to the temporary list t.
  4. Backtracking: After exploring the option with the current candidate included, we backtrack by removing it from the combination using t.pop() to restore the state for other explorations.

  5. Avoiding Duplicates: Sorting candidates and ensuring that we always start with the smallest possible candidate for each slot in a combination avoid duplication naturally because each combination will be built up in a sorted manner.

  6. Execution: We initialize the list to store our temporary and final answers, t and ans, respectively, and start our DFS with dfs(0, target).

This approach ensures that we thoroughly explore all viable combinations of candidates that can add up to target, respecting the constraint of unique frequency for each number within the combinations.

Solution Approach

The implementation of the solution utilizes a dfs function that orchestrates a recursive depth-first search to explore different combinations. Let’s dissect how the algorithm, data structures, and patterns work in tandem:

  1. Algorithm: The key algorithmic technique here is backtracking, which is a type of DFS. Backtracking is a systematic way to iterate through all the possible configurations of a search space. It is designed to decompose a complex problem into simpler subproblems. If the current solution is not workable or optimal, it's abandoned (hence the term 'backtrack').

  2. Data Structures: We use two lists in this solution - ans to store the final list of combinations and t as a temporary list to keep an ongoing combination. These lists are essential to gather the result and to maintain the state during recursion.

  3. Patterns: The implementation follows a common pattern found in DFS/backtracking solutions called "decide-explore-un-decide". At every step, we make a decision (include the current candidate or not), explore further down the path (recursive call), and then undo the decision (pop the candidate).

Let's review the implementation step-by-step with a reference to the code:

1def dfs(i: int, s: int):
2    if s == 0:
3        ans.append(t[:])  # Found valid combination
4        return
5    if i >= len(candidates) or s < candidates[i]:
6        return  # Cannot go further, backtrack
7    dfs(i + 1, s)  # Skip current candidate and explore further
8    t.append(candidates[i])  # Include current candidate
9    dfs(i, s - candidates[i])  # Continue with the included candidate
10    t.pop()  # Remove the last candidate and explore other possibilities

This block of code is the heart of the solution. The dfs function is called recursively to explore each candidate:

  • Checking for Completion: If s is 0, we've matched our target, so we copy the current list t to our answer list ans.
  • Termination Conditions: If i is out of range or the current candidate is larger than s, we cannot find a valid combination on this path, so we return to explore a different path.
  • Exploring Without the Current Candidate: If we call dfs(i + 1, s), we're exploring possibilities without the current candidate.
  • Including the Current Candidate: By adding candidates[i] to t before making the recursive call, we explore the option where we include the current candidate.
  • Backtracking: After the recursive call that includes the candidate returns, we pop that candidate from t. This step is essential, as it brings us back to the decision point where we did not include the candidate - all set for the next iteration.

The initial call to dfs(0, target) kickstarts the exploration. Given that we sorted candidates at the beginning, the DFS will proceed from the smallest to the largest candidate, which again helps in avoiding duplicates and unnecessary explorations. As we accumulate combinations, they are stored in the ans list, which we eventually return as the result.

In summary, the solution implements a backtracking DFS strategy to generate all possible unique combinations of numbers that add up to a target sum. This method is both efficient and a classic example of how problems involving combinations can be solved.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a small example to illustrate the solution approach with the candidates list as [2, 3, 6] and a target of 7.

  1. Sorting Candidates: Firstly, the candidates list [2, 3, 6] is sorted, yielding the same list as it is already sorted.

  2. Initial Call: We begin the search by calling dfs(0, 7) implying that we start with the first candidate and the target sum of 7.

  3. First Exploration:

    • We did not reach a base case yet, so we try dfs(0 + 1, 7) which is dfs(1, 7). We're skipping the first candidate (2) and exploring the next candidate (3).
    • Simultaneously, we try the other path where we include the first candidate (2) by calling dfs(0, 5), since 7 - 2 = 5. Our temporary combination list t now has [2].
  4. Exploration with Second Candidate:

    • In the call for dfs(1, 7), we repeat the process. Again, it splits into two recursive calls: dfs(2, 7) (skipping the current candidate, 3) and dfs(1, 4) (including the current candidate, 3). Now t = [3].
    • Meanwhile, exploring the other branch with dfs(0, 5), we again include the first candidate, making the recursive call dfs(0, 3). The list t is now [2, 2].
  5. Finding a Combination:

    • Continuing with dfs(0, 3), we yet again choose to include the first candidate. Now, dfs(0, 1) is called and t = [2, 2, 2].
    • With dfs(0, 1), we can no longer include 2 as it's greater than the target, so we explore with the next candidate by calling dfs(1, 1). Since there isn't a candidate with value 1, this path doesn't yield a valid combination, and we backtrack.
    • Backtracking to dfs(0, 3), we pop out the last candidate and try dfs(1, 3). Since 3 is a candidate, we find a combination [2, 2, 3] which adds up to 7, so that is added to our ans list.
  6. Continued Exploration and Backtracking:

    • We continue this process, exploring different permutations and excluding those that exceed the target sum. All the while, we backtrack correctly by removing the last added candidate from t upon going up a level in the search tree.
  7. Result: Eventually, we end up with the ans list containing all unique combinations that sum up to 7, which could be [[2, 2, 3]] in this small example.

The complete process involved recursively selecting candidates until we reached the target or exceeded it. This methodically covered all possible unique combinations, ensuring that we met the problem’s conditions effectively.

Python Solution

1from typing import List  # Import necessary List type from the typing module for type annotation
2
3class Solution:
4    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
5        # Helper function to perform depth-first search for combinations
6        def dfs(index: int, current_sum: int):
7            # Check if the current combination equals target sum
8            if current_sum == 0:
9                # If current sum is zero, we found a valid combination, add it to the answer list
10                combinations.append(combination_so_far[:])
11                return
12            if index >= len(candidates) or current_sum < candidates[index]:
13                # If we've reached the end of candidates array or current_sum
14                # is less than the candidate at the index, stop exploring this path
15                return
16            # Recurse without including the current candidate
17            dfs(index + 1, current_sum)
18            # Choose the current candidate
19            combination_so_far.append(candidates[index])
20            # Recurse including the current candidate
21            dfs(index, current_sum - candidates[index])
22            # Backtrack by removing the current candidate
23            combination_so_far.pop()
24
25        # Sort the candidates to help with early stopping in dfs
26        candidates.sort()
27        # This is a temporary list to hold the current combination
28        combination_so_far = []
29        # This is the list to hold all unique combinations that sum up to target
30        combinations = []
31        # Start the dfs from the first candidate with the summation equal to target
32        dfs(0, target)
33        # Return all unique combinations found
34        return combinations
35

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    private List<List<Integer>> combinations = new ArrayList<>(); // Store the list of all combinations
7    private List<Integer> currentCombination = new ArrayList<>(); // Current combination being explored
8    private int[] candidateNumbers; // Array of candidate numbers
9
10    // Method to find all unique combinations where the candidate numbers sum up to target
11    public List<List<Integer>> combinationSum(int[] candidates, int target) {
12        Arrays.sort(candidates); // Sort the array of candidates to optimize the process
13        this.candidateNumbers = candidates; // Store the global reference for candidate numbers
14        backtrack(0, target);
15        return combinations;
16    }
17
18    // Helper method to perform the depth-first search
19    private void backtrack(int startIndex, int remainingSum) {
20        if (remainingSum == 0) {
21            // If the remaining sum is 0, we found a valid combination
22            combinations.add(new ArrayList<>(currentCombination));
23            return;
24        }
25        if (startIndex >= candidateNumbers.length || remainingSum < candidateNumbers[startIndex]) {
26            // If startIndex is out of bounds or the smallest candidate exceeds remainingSum
27            return;
28        }
29      
30        // Skip the current candidate and move to the next one
31        backtrack(startIndex + 1, remainingSum);
32
33        // Include the current candidate in the current combination
34        currentCombination.add(candidateNumbers[startIndex]);
35        // Continue exploring with the current candidate (since we can use the same number multiple times)
36        backtrack(startIndex, remainingSum - candidateNumbers[startIndex]);
37        // Backtrack and remove the last element before trying the next candidate
38        currentCombination.remove(currentCombination.size() - 1);
39    }
40}
41

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <functional>
4
5class Solution {
6public:
7    // Finds all unique combinations of candidates that sum up to the given target
8    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
9        // Sort the candidates to improve efficiency and ensure combinations are found in order
10        std::sort(candidates.begin(), candidates.end());
11      
12        std::vector<std::vector<int>> combinations; // Final result; a list of all combinations
13        std::vector<int> currentCombo;              // Current combination being explored
14      
15        // The recursive function to perform depth-first search to find all combinations
16        std::function<void(int, int)> depthFirstSearch = [&](int index, int remaining) {
17            // If remaining sum is zero, we have found a valid combination
18            if (remaining == 0) {
19                combinations.emplace_back(currentCombo);
20                return;
21            }
22            // If we've exhausted all candidates or the remaining sum is too small, backtrack
23            if (index >= candidates.size() || remaining < candidates[index]) {
24                return;
25            }
26          
27            // Skip the current candidate and move to the next one
28            depthFirstSearch(index + 1, remaining);
29          
30            // Include the current candidate and continue searching with reduced remaining sum
31            currentCombo.push_back(candidates[index]);
32            depthFirstSearch(index, remaining - candidates[index]);
33          
34            // Backtrack: remove the last candidate from the current combo
35            currentCombo.pop_back();
36        };
37      
38        // Start the depth-first search, starting from the first candidate and target sum
39        depthFirstSearch(0, target);
40      
41        return combinations;
42    }
43};
44

Typescript Solution

1function combinationSum(candidates: number[], target: number): number[][] {
2    // Sort the array to handle combinations in ascending order.
3    candidates.sort((a, b) => a - b);
4
5    // This will hold all unique combinations that sum up to the target.
6    const combinations: number[][] = [];
7
8    // Temporary array to store the current combination.
9    const currentCombination: number[] = [];
10
11    // Helper function to find all combinations.
12    const findCombinations = (startIndex: number, remainingSum: number) => {
13        // If remaining sum is zero, we found a valid combination.
14        if (remainingSum === 0) {
15            combinations.push(currentCombination.slice());
16            return;
17        }
18
19        // If the startIndex is outside the bounds or the smallest candidate
20        // is larger than the remaining sum, there's no point in exploring further.
21        if (startIndex >= candidates.length || remainingSum < candidates[startIndex]) {
22            return;
23        }
24
25        // Skip the current candidate and move to the next.
26        findCombinations(startIndex + 1, remainingSum);
27
28        // Include the current candidate and explore.
29        currentCombination.push(candidates[startIndex]);
30        findCombinations(startIndex, remainingSum - candidates[startIndex]);
31
32        // Backtrack and remove the current candidate from the current combination.
33        currentCombination.pop();
34    };
35
36    // Initialize the recursive function with the starting index and initial target sum.
37    findCombinations(0, target);
38    return combinations;
39}
40

Time and Space Complexity

Time Complexity

The time complexity of the given code primarily depends on the number of potential combinations that can be formed with the given candidates array that sum up to the target. Considering the array has a length n and the recursion involves iterating over candidates and including/excluding them, we get a recursion tree with a depth that could potentially go up to target/min(candidates), if we keep using the smallest element. This leads to an exponential number of possibilities. Thus, the time complexity of the algorithm is O(2^n) in the worst case, when the recursion tree is fully developed. However, since we often return early when s < candidates[i], this is an upper bound.

Space Complexity

The space complexity of the algorithm is also important to consider. It is mainly used by recursion stack space and the space to store combinations. The maximum depth of the recursion could be target/min(candidates) which would at most be O(target) if 1 is in the candidates. However, the space required for the list t, which is used to store the current combination, is also dependent on the target and could at most have target elements when 1 is in the candidates. The space for ans depends on the number of combinations found. Since it's hard to give an exact number without knowing the specifics of candidates and target, we consider it for the upper bound space complexity. Thus, as the list ans grows with each combination found, in the worst case, it could store a combination for every possible subset of candidates, leading to a space complexity of O(2^n * target), where 2^n is the number of combinations and target is the maximum size of any combination.

However, if we look at the auxiliary space excluding the space taken by the output (which is the space ans takes), then the space complexity is O(target) due to the depth of the recursive call stack and the temporary list t.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫