Brute force Approach ( Using Recursion)
We will create a recursive function “findCombination” helper function which will recursively find all combinations that sum up to the target. The base case for function is when the Current Sum equals the target, pushing the Current Combination to the answer array. Recursively call the function and consider two possibilities either we have to pick the element and add it to current Sum or we will skip the current element.
Example: To demonstrate Combination sum problem using recursive approach.
function combinationSum(nums, target) {
// Helper function
function findCombinations(start, currentSum
, currentCombination) {
// Base case
if (currentSum === target) {
result.push([...currentCombination]);
return;
}
// one more edge case
if (currentSum > target || start === nums.length) {
return;
}
// include current element
findCombinations(start, currentSum + nums[start],
currentCombination.concat(nums[start]));
// exclude current element
findCombinations(start + 1, currentSum, currentCombination);
}
const result = [];
findCombinations(0, 0, []);
// Return
return result;
}
const nums = [2, 3, 6, 7];
const target = 7;
console.log("possible combinations are : ",
combinationSum(nums, target));
Output
possible combinations are : [ [ 2, 2, 3 ], [ 7 ] ]
Time Complexity: O(2n)
Space Complexity: O(n*m)
Combination Sum Problem in JavaScript
In the Combination problem we are given an array of integers and a target number, we have to return all unique possible combinations whose element sum is equal to the target value.
There are several approaches available in JavaScript to solve the combination sum problem which are as follows:
Table of Content
- Brute force Approach ( Using Recursion)
- Optimal Approach (Using Dynamic Approach)
Contact Us