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. 7 is a candidate. Hence the result.

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. Hence the result.

Steps

1. Backtracking: We will use a backtracking approach to explore all possible combinations.
2. Recursive Function: A recursive function will explore combinations. It takes the current index, the current combination, and the remaining target sum as input.
3. Base Cases:
   • If the remaining target is 0, we've found a valid combination; add it to the result and return.
   • If the remaining target is negative or we've reached the end of the candidates array, we backtrack (return).
4. Recursive Step: For each candidate at the current index, we:
   • Add the candidate to the current combination.
   • Recursively call the function with the updated combination and remaining target.
   • Remove the candidate from the current combination (backtracking) to explore other possibilities.

Explanation

The backtracking algorithm systematically explores all possible combinations by making choices (adding candidates) and undoing those choices (removing candidates). The recursive calls branch out to explore different possibilities, and once a combination sums to the target, it's added to the result. The use of vector<int> for combination makes it easy to build up and modify the current combination during the recursive calls. The removal of the last element during backtracking ensures that we don't overcount combinations and maintain uniqueness

Code

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> combination;
        backtrack(candidates, target, 0, combination, result);
        return result;
    }

private:
    void backtrack(const std::vector<int>& candidates, int target, int index, std::vector<int>& combination, std::vector<std::vector<int>>& result) {
        if (target == 0) {
            result.push_back(combination);
            return;
        }
        if (target < 0 || index >= candidates.size()) {
            return;
        }

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

        // Exclude the current candidate (backtracking)
        combination.pop_back();
        backtrack(candidates, target, index + 1, combination, result); //Explore with the next candidate

    }
};

Complexity

• Time Complexity: O(N^T), where N is the number of candidates and T is the target value. In the worst case, we might explore all possible combinations.
• Space Complexity: O(T) in the worst case, due to the recursive call stack and the maximum depth of the recursion, which is proportional to the target value. The space used to store the result is also proportional to the number of combinations found which is bounded by a small constant (less than 150) as stated in the problem description.