This approach uses recursion and backtracking to generate all possible combinations by exploring each candidate. If a candidate is chosen, we explore further with the remaining target reduced by the candidate's value. We use backtracking to remove a candidate and try the next one. This way, we explore all possible combinations using depth-first search.
Time Complexity: O(2^T), where T is the target, as it potentially explores every combination of the candidates.
Space Complexity: O(T) for the recursion call stack and the path being explored.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5void backtrack(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int>& combination, int start) {
6 if (target < 0) return;
7 if (target == 0) {
8 result.push_back(combination);
9 return;
10 }
11 for (int i = start; i < candidates.size(); ++i) {
12 combination.push_back(candidates[i]);
13 backtrack(candidates, target - candidates[i], result, combination, i);
14 combination.pop_back();
15 }
16}
17
18vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
19 vector<vector<int>> result;
20 vector<int> combination;
21 backtrack(candidates, target, result, combination, 0);
22 return result;
23}
24
25int main() {
26 vector<int> candidates = {2, 3, 6, 7};
27 int target = 7;
28 vector<vector<int>> result = combinationSum(candidates, target);
29 for (const auto& comb : result) {
30 cout << "[";
31 for (int i = 0; i < comb.size(); ++i) {
32 cout << comb[i] << (i == comb.size() - 1 ? "" : ", ");
33 }
34 cout << "]\n";
35 }
36 return 0;
37}
38The C++ solution employs backtracking through recursion. It maintains a helper backtrack function, exploring each combination by choosing candidates and iterating from the current index to allow reuse. Combinations resulting in zero target are added to the result set.
We can use a dynamic programming (DP) approach to solve the Combination Sum problem. We maintain a DP array where each index represents the number of ways to form that particular sum using the candidates. The approach involves iterating through candidates and updating the DP array for each possible sum that can be formed with that candidate.
Time Complexity: Roughly O(T * N), for target T and candidates N.
Space Complexity: O(T) for the dp array itself in context of storage.
1using System;
2using System.Collections.Generic;
3
4class CombinationSumDPSolution {
5 public IList<IList<int>> CombinationSum(int[] candidates, int target) {
6 List<IList<int>>[] dp = new List<IList<int>>[target + 1];
7 dp[0] = new List<IList<int>> { new List<int>() };
8
9 for (int i = 1; i <= target; i++) {
10 dp[i] = new List<IList<int>>();
11 foreach (int candidate in candidates) {
12 if (i >= candidate) {
13 foreach (var combination in dp[i - candidate]) {
14 var newComb = new List<int>(combination);
15 newComb.Add(candidate);
16 dp[i].Add(newComb);
17 }
18 }
19 }
20 }
21 return dp[target];
22 }
23
24 static void Main(string[] args) {
25 int[] candidates = {2, 3, 6, 7};
26 int target = 7;
27 CombinationSumDPSolution solution = new CombinationSumDPSolution();
28 var result = solution.CombinationSum(candidates, target);
29 foreach (var combination in result) {
30 Console.WriteLine("[" + string.Join(", ", combination) + "]");
31 }
32 }
33}
34In C#, the DP approach initializes arrays at indices corresponding to all sums up to target using candidates progressively, storing all valid combinations for each sum index after iterating through possible sums.