Print variations DP
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
const NUMS = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const SUM = 100;
function printVariation(operators, numbers) {
const sequence = [numbers[0]];
operators.forEach((o, index) => {
sequence.push(o);
sequence.push(numbers[index + 1]);
});
console.log(sequence.join(' '));
}
function joinNumbers(operators, numbers, currentSum, iteration) {
const joinedNumbers = numbers.slice();
const prevNum = joinedNumbers[joinedNumbers.length - 1];
const joinedNum = prevNum * 10 + NUMS[iteration];
let updatedSum = currentSum;
joinedNumbers[joinedNumbers.length - 1] = joinedNum;
if(operators.length) {
prevOperation = operators[operators.length - 1];
if (prevOperation === '+') {
updatedSum -= prevNum;
updatedSum += joinedNum;
} else {
updatedSum += prevNum;
updatedSum -= joinedNum;
}
} else {
updatedSum = joinedNum;
}
return {
joinedNumbers,
updatedSum
}
}
function findVariations(operators = [], numbers = [NUMS[0]], currentSum = NUMS[0] , iteration = 1) {
if (iteration > 8) {
if (currentSum === SUM) {
printVariation(operators, numbers);
}
return;
}
const nextNumbers = numbers.slice();
nextNumbers.push(NUMS[iteration]); // Next number for '+' and '-'
const v1 = operators.slice();
v1.push('+');
findVariations(v1, nextNumbers, currentSum + NUMS[iteration], iteration + 1);
const v2 = operators.slice();
v2.push('-')
findVariations(v2, nextNumbers, currentSum - NUMS[iteration], iteration + 1);
// Join two numbers
const { joinedNumbers, updatedSum } = joinNumbers(operators, numbers, currentSum, iteration);
findVariations(operators, joinedNumbers, updatedSum, iteration + 1);
}
findVariations();
JavaScript
INFO