Create array of all N digit numbers whose sum of digit equals S

Question

I found some solutions to my question in other languages. When I converted them to javascript, it would not create an array.

const find_digits = (n, sum, out, index) => {
    if (index > n || sum < 0) return;
    let f = "";
    if (index == n) {
        if (sum == 0) console.log(out); // Success!
        return;
    }
    for (var i = 0; i < 10; i++) {
        out[index] = i;
        find_digits(n, sum - i, out, index + 1);
    }
}
const subset_sum = (n, sum) => {
    var out = [].fill(false, 0, n + 1);
    for (var i = 0; i < 10; i++) {
        out[0] = i;
        find_digits(n, sum - i, out, 1);
    }
    return out;
}
console.log(subset_sum(3, 17)); // Output: [9,9,9]

The first log is successful, but the final log returns [9,9,9] I would appreciate some help.

Answer 1

I might make the recursion a bit more explicit. To my mind there are a number of different base-cases, for various low values of n and s:

• if s < 0, then there are no results
• if s == 0, then the only result is a string of n zeroes
• if n == 1, then
  • if s < 10, then the only result is the digit s
  • otherwise, there are no results

The recursive case involves taking each digit as a potential first digit, then joining it with each of the results involved in recursing, taking that amount from the total and using a digit count one smaller.

Here's an implementation of that:

const subsetSum = (n, s) =>
  s < 0
    ? []
  : s == 0
    ? ['0' .repeat (n)]
  : n == 1
    ? s < 10 ? [String(s)] : []
  : // else 
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] .flatMap (
       k => subsetSum (n - 1, s - k) .map (p => k + p)
    )


console .log (
  subsetSum (3, 17)  
) //~> ["089", "098", "179", "188", "197", "269", "278", ..., "971", "980"] (63 entries)

.as-console-wrapper {min-height: 100% !important; top: 0}

Given your comment about licenses, I assume that it's really strings of digits you want and not numbers. That's what this returns. If you want numbers, you will need to remove all those that start with 0 and convert the strings to numbers. (Thus, 89 would not be included in subset(17, 3) even thought "089" is a legitimate digit string, because 89 is only a two-digit number.)

Update

I just realized that the s == 0 case can be subsumed in the recursive one. So it's actually a bit simpler:

const subsetSum = (n, s) =>
  s < 0
    ? []
  : n == 1
    ? s < 10 ? [String(s)] : []
  : // else 
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] .flatMap (
       k => subsetSum (n - 1, s - k) .map (p => k + p)
    )

Or, phrased slightly differently, as

const subsetSum = (n, s) =>
  s < 0 || (n <= 1 && s >= 10)
    ? []
  : n == 1
    ? [String(s)] 
  : // else 
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] .flatMap (
       k => subsetSum (n - 1, s - k) .map (p => k + p)
    )

Answer 2

    const find_digits = (n, sum, out, index) => {
    if (index >= n) return;
     out[index] = 9;
  find_digits(n, sum, out, index +1);
}
const subset_sum = (n, sum) => {
    var out = [].fill(false, 0, n + 1);
        find_digits(n, sum, out, 0);
    return out;
}
console.log(subset_sum(3, 17));

I guess the problem is with the check at the beginning of the find_digit() function for the number of times you can call this function won't exceed by any means 3 times as per your arguments passed in the subset_sum() function. I have redacted the code to the bare minimum and produced the same result as yours. If you can give me clarification as to the purpose of this code. I would be glad to help.

Answer 3

You should call your function without console, like this: subset_sum(3, 17) Because you write to console inside your code. Your trouble is that your subset_sum returning at the end array out. So, you have 2 options: - call your function by name - returning at the end of subset_sum just "return"

Answer 4

The function below allows you to pass in a different base/alphabet.

It first generates the permutations, then filters the results based on the value you passed in as the second parameter.

const BaseSystem = {
  bin : '01',
  dec : '0123456789',
  hex : '0123456789ABCDEF'
};
Object.keys(BaseSystem).forEach(k =>
  Object.assign(BaseSystem, { [k] : BaseSystem[k].split('') }))

const main = () => {
  console.log(subsetSum(4, v => v === 2, BaseSystem.bin))  
  console.log(subsetSum(2, 4))  // Default = BaseSystem.dec
  console.log(subsetSum(3, 0xF, BaseSystem.hex))
}

const subsetSum = (size, sum, alpha=BaseSystem.dec) => {
  if (typeof sum === 'string') sum = parseInt(sum, alpha.length)
  return getPermutations(alpha, size)
    .filter(v => ((result) =>
      typeof sum === 'function' ? sum(result, v) : sum === result
    )(parseReduce(alpha.length, ...v))).map(v => v.join(''))
}

const parseReduce = (base, ...v) =>
  v.reduce((t, x) => t + parseInt(x, base), 0)

/** Adapted From: https://stackoverflow.com/a/59028925/1762224 */
const getPermutations = (list, len) => {
  const base = list.length
  const counter = Array(len).fill(base === 1 ? arr[0] : 0)
  if (base === 1) return [counter]
  const results = []
  const increment = i => {
    if (counter[i] === base - 1) {
      counter[i] = 0
      increment(i - 1)
    } else counter[i]++
  }
  for (let i = base ** len; i--;) {
    const subResults = []
    for (let j = 0; j < counter.length; j++)
      subResults.push(list[counter[j]])
    results.push(subResults)
    increment(counter.length - 1)
  }
  return results
}

main();

.as-console-wrapper {min-height: 100% !important; top: 0}