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.
1def combinationSum(candidates, target):
2 def backtrack(remaining, path, start):
3 if remaining < 0:
4 return
5 if remaining == 0:
6 result.append(list(path))
7 return
8 for i in range(start, len(candidates)):
9 path.append(candidates[i])
10 backtrack(remaining - candidates[i], path, i)
11 path.pop()
12
13 result = []
14 backtrack(target, [], 0)
15 return result
16
17candidates = [2, 3, 6, 7]
18target = 7
19print(combinationSum(candidates, target))
20This Python implementation defines a recursive backtrack function to explore and solve the problem by selecting candidates starting from the current index for potential reuse, stopping when the target is met or surpassed.
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.
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
7 vector<vector<int>> dp[target + 1];
8 dp[0] = {{}}; // Base condition
9
10 for (int i = 1; i <= target; i++) {
11 for (const int& cand : candidates) {
12 if (i >= cand) {
13 for (auto& subResult : dp[i - cand]) {
14 dp[i].push_back(subResult);
15 dp[i].back().push_back(cand);
16 }
17 }
18 }
19 }
20
21 return dp[target];
22}
23
24int main() {
25 vector<int> candidates = {2, 3, 6, 7};
26 int target = 7;
27 vector<vector<int>> result = combinationSum(candidates, target);
28 for (const auto& comb : result) {
29 cout << "[";
30 for (int i = 0; i < comb.size(); ++i) {
31 cout << comb[i] << (i == comb.size() - 1 ? "" : ", ");
32 }
33 cout << "]\n";
34 }
35 return 0;
36}
37The C++ solution defines a DP table where each entry at index i stores all combinations that sum to i using combinations of previous entries combined with current candidates.