• Posts

Problem 39 Combination Sum

Problem Statement

Link - Problem 39

Question

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

Solution

class Solution {
public:
    vector<vector<int>> ans;
    void solve(int i, vector<int>& arr, vector<int>& temp, int target)
    {
        if(target == 0)
        {
            ans.push_back(temp);
            return;
        }

        if(target < 0)
            return;

        if(i == arr.size())
            return;
        solve(i + 1, arr, temp, target);

        temp.push_back(arr[i]);
        solve(i, arr, temp, target - arr[i]);
        temp.pop_back();

    }
    vector<vector<int>> combinationSum(vector<int>& arr, int target) {
        ans.clear();
        vector<int> temp;
        solve(0, arr, temp, target);
        return ans;
    }
};

Complexity Analysis

| Algorithm    | Time Complexity | Space Complexity |
| ------------ | --------------- | ---------------- |
| Backtracking | O(n 2^n)        | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we need to think about how to break down the target number into smaller parts using the given candidates. Key points to consider are: the same number can be used unlimited times, the order of the numbers doesn’t matter, and we only need unique combinations. We can approach this by thinking of it as a tree where each node represents adding a number to our current sum, and we can prune branches that exceed the target. Additionally, considering the constraints that the number of unique combinations is less than 150 can help us focus on efficient exploration of possible combinations. We also need to think about how to keep track of the combinations we’ve already found to avoid duplicates. Lastly, an understanding of backtracking will be crucial to efficiently explore all possible combinations.

Intuitive Analysis

Intuitively, solving this problem involves visualizing a recursive process where we try adding each candidate number to our current sum, and then recursively try adding more numbers until we reach the target or exceed it. If we exceed the target, we stop exploring that branch. If we reach the target, we’ve found a valid combination. We need to think about how to implement this recursive process in a way that avoids redundant calculations and efficiently explores all possible combinations. This involves considering how to organize our recursive calls, how to keep track of the current combination being explored, and how to avoid exploring the same combination multiple times. By breaking down the problem into these smaller pieces and considering how they fit together, we can build an intuitive understanding of how to find all unique combinations that sum to the target.

1. Intuition

• The problem can be approached using a recursive backtracking strategy, exploring all possible combinations of candidates that sum up to the target.
• The key insight is to consider each candidate as a potential starting point for a combination, and then recursively explore all possible combinations that can be formed by adding more candidates.
• The base cases for the recursion are when the target becomes 0 (indicating a valid combination has been found) or when the target becomes negative (indicating an invalid combination).
• The problem also requires considering the same candidate multiple times, which can be achieved by passing the same index to the recursive function.
• The solution should also handle the case where the target cannot be reached with the given candidates, in which case an empty list should be returned.
• The algorithmic choice of using recursion allows for a clean and efficient implementation of the backtracking strategy.
• The time complexity of the solution is exponential due to the recursive nature of the algorithm, but it is guaranteed to find all possible combinations that sum up to the target.

2. Implementation

• The solve function is a recursive function that takes the current index i, the array of candidates arr, a temporary array temp to store the current combination, and the remaining target value target.
• The if (target == 0) condition checks if a valid combination has been found, in which case the temp array is added to the ans vector.
• The if (target < 0) condition checks if the current combination exceeds the target, in which case the function returns without adding the combination to the ans vector.
• The solve(i + 1, arr, temp, target) call explores the next candidate in the array, effectively skipping the current candidate.
• The temp.push_back(arr[i]) and solve(i, arr, temp, target - arr[i]) calls add the current candidate to the current combination and recursively explore all possible combinations that can be formed by adding more candidates.
• The temp.pop_back() call backtracks by removing the last added candidate from the current combination, allowing the function to explore other branches of the recursion tree.
• The combinationSum function initializes the ans vector and calls the solve function with the initial index, array, and target value.

Complexity Analysis

Time Complexity:

• The time complexity is dominated by the recursive calls in the solve function. In the worst-case scenario, the function can make up to 2^n calls, where n is the number of elements in the input array. Additionally, within each call, we are creating a copy of the current path in the ans vector, which takes O(n) time. Hence, the overall time complexity is O(2^n * n), which accounts for both the recursive calls and the copying of paths.
• The solve function is called recursively with two different branches: one that includes the current element (solve(i, arr, temp, target - arr[i])) and one that excludes it (solve(i + 1, arr, temp, target)). This branching factor of 2 at each step leads to a total of 2^n possible paths, making the time complexity exponential.
• To justify the Big O classification of O(2^n * n), we consider the worst-case scenario where the input array contains only ones and the target sum is equal to the number of elements in the array. In this case, the function will explore all possible combinations of elements, resulting in 2^n recursive calls, each taking O(n) time.

Space Complexity:

• The space complexity is primarily influenced by the recursion stack and the storage of result combinations in the ans vector. In the worst-case scenario, the recursion stack can grow up to a depth of n, corresponding to the maximum recursion depth.
• The temp vector, used to store the current combination of elements, can also grow up to a size of n in the worst-case scenario. Additionally, the ans vector stores all valid combinations found during the backtracking process, which can require up to O(n) space in the worst case.
• To justify the space complexity of O(n), we consider that the maximum recursion depth and the size of the temp and ans vectors are all bounded by the number of elements in the input array, resulting in a linear space complexity.

Footnote

This question is rated as Medium difficulty.

Similar Questions: