Optimal Approach (Using Dynamic Approach)
We use recursion + memoization i.e. top-down dynamic programming approach. Initialize an empty object to store computed results. Define a nested function, dp, for recursive combination finding with memoization. Handle base cases and iterate over nums, recursively calling dp with updated target, then concatenate num with each combination obtained and push to res. Memoize res with the current target as the key. Return the result obtained from dp for the given target.
Example: To demonstrate Combination sum problem using recursion with memoization
function combinationSum(nums, target) {
const memo = {};
// remove duplicates from the array
nums = nums.sort((a, b) => a - b).filter((num, index, arr)
=> index === 0 || num !== arr[index - 1]);
function dp(start, target) {
if (memo[target]) {
return memo[target];
}
if (target === 0) {
return [[]];
}
if (target < 0) {
return [];
}
const res = [];
for (let i = start; i < nums.length; i++) {
const num = nums[i];
if (target - num >= 0) {
for (const comb of dp(i, target - num)) {
res.push([num, ...comb]);
}
}
}
memo[target] = res;
return res;
}
return dp(0, target);
}
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(n2 * m)
Space Complexity: O(m * k)
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