1.6) Find Combination Sum to Target

Given an array of distinct integers candidates and a target integer target, return all possible combinations of candidates where the chosen numbers sum to target. You may use the same number multiple times. The combinations should be returned in any order.

Sample Input/Output:

Sample input:

candidates = [2, 3, 6, 7]
target = 7

Expected Output:

[
  [2, 2, 3],
  [7]
]

Explanation:
For the given input [2, 3, 6, 7] and target = 7, there are two possible combinations:

1. [2, 2, 3]: The chosen numbers sum to the target 7.
2. [7]: The chosen number 7 directly sums to the target 7.

Time and Space Complexity:

The time complexity of the solution will be O(N * 2^N), where N is the number of elements in the candidates array. For each element, there are 2 choices: either include it in the combination or exclude it. The number of possible combinations is 2^N.

The space complexity will be O(N * 2^N) to store all possible combinations.

C++ Solution:

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> currentCombination;

    // Helper function to backtrack and generate combinations
    void backtrack(int start, int currentSum) {
        if (currentSum == target) {
            result.push_back(currentCombination);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            int candidate = candidates[i];
            if (currentSum + candidate <= target) {
                currentCombination.push_back(candidate);
                backtrack(i, currentSum + candidate); // Note that we can reuse the same element, so the start index is 'i'
                currentCombination.pop_back();
            }
        }
    }

    backtrack(0, 0);

    return result;
}

int main() {
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    vector<vector<int>> result = combinationSum(candidates, target);

    cout << "Combinations for target " << target << ":\n";
    for (const auto& combination : result) {
        cout << "[";
        for (int num : combination) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

In this implementation, we use backtracking to generate all possible combinations. The backtrack function is a recursive function that explores all possible choices for each element in the candidates array. It uses a currentSum variable to keep track of the current sum of elements in the combination.

The backtrack function includes an element in the current combination and makes a recursive call with the same start index to allow reusing the same element multiple times if needed. When the current sum matches the target, the combination is added to the result.

The main function demonstrates the usage of combinationSum by finding all possible combinations for the given input candidates and target.

The output will be:

Combinations for target 7:
[2 2 3 ]
[7 ]