List all the ways that 1, 2, and 3 can add up to 4, the order matters. For example, [1, 1, 1, 1] is one way. [1,1,2] is different from [1,2,1]
I have figured out one way it works on paper. But I still cannot write the code for it. Please help and Please check out this picture of My Idea for clarity.
This code I wrote failed. But this is how far I've got.
function theseAddToSum(steps = [], sum) {
let results = [];
if (steps.length < 1) return 'error'
for (let i = 0; i < steps.length; i++) {
let cur = steps[i];
let remaining = sum - cur;
if (remaining >= 0) {
console.log('sum', sum, 'step', cur)
let c = theseAddToSum(steps, remaining)
}
}
return results
}
console.log(theseAddToSum([1, 2, 3], 4))
As I console.log('sum', sum, 'step', cur), I get the desired results:
sum 4 step 1
sum 3 step 1
sum 2 step 1
sum 1 step 1
sum 2 step 2
sum 3 step 2
sum 1 step 1
sum 3 step 3
sum 4 step 2
sum 2 step 1
sum 1 step 1
sum 2 step 2
sum 4 step 3
sum 1 step 1
My problem is that I don't know how to push the result to results array. It should look like [[1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], and on]
Some issues:
Although the array returned by the recursive call is captured in the variable c, that variable is not used further on, and so it has been useless.
results is initialised as [], but is then never modified/extended, so the final return result is guaranteed to return that empty list.
The above two issues need to be solved by iterating the solutions present in c: append the current value to those solutions (since we had subtracted that value to get those solutions), and append those extended solutions to the current results array.
When remaining is equal to 0, it makes no sense to make more recursive calls. This is actually a base case of the recursion. (I prefer to do this check one level deeper in the recursion, at the start of the function: if the sum is 0, we should return an empty solution which can then be extended by the selected values as we get back out of recursion).
Unrelated, but it is better practice to separate your statements with semicolons. You wouldn't be the first to fall in one of the traps of automatic semicolon insertion. Better take control.
Here is a corrected version:
function theseAddToSum(steps = [], sum) {
// Base cases:
if (sum < 0) return []; // No solutions
if (sum == 0) return [[]]; // A solution
let results = [];
if (steps.length < 1) return 'error';
for (let i = 0; i < steps.length; i++) {
let cur = steps[i];
let remaining = sum - cur;
let c = theseAddToSum(steps, remaining)
// Use the solutions we got back from recursion
for (let solution of c) {
solution.push(cur); // ... then extend them
results.push(solution); // ... and collect them
}
}
return results;
}
console.log(theseAddToSum([1, 2, 3], 4));
This is a perfect opportunitiy to use backtracking. The idea of backracking is that we set out to try all possible combinations, but when our current combination fails and we can't continue building upon it, then we go back and try something else.
The way we approach a backtracking problem is this:
[1,2,3]solution arrayThat's a lot of words, let's solve the question:
const getSum = (arr) => arr.reduce((acc, num) => num + acc, 0);
function theseAddToSum(steps, sum) {
const solutions = [];
function recurse(steps, sum, currentSol) {
if (getSum(currentSol) === sum) {
solutions.push([...currentSol]);
return
}
for (let i = 0; i < steps.length; i++) {
currentSol.push(steps[i]);
if (getSum(currentSol) <= sum) {
recurse(steps, sum, currentSol);
}
currentSol.pop();
}
}
recurse(steps, sum, [])
return solutions;
}
console.log(theseAddToSum([1, 2, 3], 4));