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.
1const combinationSum = function(candidates, target) {
2 const result = [];
3
4 function backtrack(remaining, path, start) {
5 if (remaining < 0) return;
6 if (remaining === 0) result.push([...path]);
7
8 for (let i = start; i < candidates.length; i++) {
9 path.push(candidates[i]);
10 backtrack(remaining - candidates[i], path, i);
11 path.pop();
12 }
13 }
14
15 backtrack(target, [], 0);
16 return result;
17};
18
19const candidates = [2, 3, 6, 7];
20const target = 7;
21console.log(combinationSum(candidates, target));
22The JavaScript solution uses the backtracking approach. It explores combinations by recursively trying candidate numbers and keeping track with path, reducing the target until zero, indicating a valid result.
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.
1const combinationSum = function(candidates, target) {
2 const dp = Array.from({ length: target + 1 }, () => []);
3 dp[0] = [[]];
4
5 for (const candidate of candidates) {
6 for (let i = candidate; i <= target; i++) {
7 for (const comb of dp[i - candidate]) {
8 dp[i].push([...comb, candidate]);
9 }
10 }
11 }
12
13 return dp[target];
14};
15
16const candidates = [2, 3, 6, 7];
17const target = 7;
18console.log(combinationSum(candidates, target));
19The JavaScript solution constructs a dp array containing arrays for every sum up to target. As candidates are iterated over, these dp arrays are generated by appending current candidates to combinations in relevant decomposed previous targets in the dp array.