I am trying to solve simple algorithm using JS:
Given two numbers n and k and you have to find all possible combination of k numbers from 1…n.
Input : n = 5
k = 3
Output : 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
However, when I tried this code using JS, I am not getting the expected output:
let ans = [],
arr = [];
function makeCombination(n, k, low = 1) {
if (k == 0) {
ans.push(arr);
console.log(...arr);
return;
}
for (let i = low; i <= n; i++) {
arr.push(i);
makeCombination(n, k - 1, i + 1);
arr.pop();
}
return ans;
}
var n = 5;
var k = 3;
makeCombination(n, k);
Output:
1 2 3
1 2 4
1 2 5
Can you please help, why I am not getting the expected output? I would appreciate any of your assistance.
let ans = [],
arr = [];
function makeCombination(n, k, low = 1) {
if (k == 0) {
ans.push(arr.slice());
// console.log(...arr); commenting out the console log to demonstrate that the returned value is correct
return;
}
for (let i = low; i <= n; i++) {
arr.push(i);
makeCombination(n, k - 1, i + 1);
arr.pop();
}
return ans;
}
var n = 5;
var k = 3;
makeCombination(n, k).map(a => console.log(...a));.as-console-wrapper { max-height: 100% !important; top: 0; }You need to make a copy of the partial results array. Otherwise you push a reference to the same array to the results array and remove the elements from it during your backtracking algorithm.
One telltale sign of the problem was that your function wrote the correct results to the console but the returned result array was populated with empty arrays. Using slice() you make a copy which avoids this problem.
Edit: Copied Nina Scholz's console formatting technique because it just looks much better.
Beside using some other variables outside of the function, you could take a function which returns a single array.
function makeCombination(n, k, i = 1) {
const result = [];
while (i <= n - k + 1) {
if (k === 1) result.push([i]);
else result.push(...makeCombination(n, k - 1, i + 1).map(a => [i, ...a]));
i++;
}
return result;
}
makeCombination(5, 3).map(a => console.log(...a));.as-console-wrapper { max-height: 100% !important; top: 0; }