1
/**
2
 * @param {string[]} words
3
 * @param {string} result
4
 * @return {boolean}
5
 */
6
var isSolvable = function (words, result) {
7
  // set to hold all the first characters
8
  const firstChars = new Set();
9

10
  // map for steps 1 & 2
11
  // this will hold the key as the character and multiple as the value
12
  let map = {};
13
  for (let i = 0; i < result.length; i++) {
14
    const char = result[i];
15
    if (!i) firstChars.add(char);
16
    if (!map.hasOwnProperty(char)) map[char] = 0;
17
    map[char] -= 10 ** (result.length - i - 1);
18
  }
19
  for (let j = 0; j < words.length; j++) {
20
    const word = words[j];
21
    for (let i = 0; i < word.length; i++) {
22
      const char = word[i];
23
      if (!i) firstChars.add(char);
24
      if (!map.hasOwnProperty(char)) map[char] = 0;
25
      map[char] += 10 ** (word.length - i - 1);
26
    }
27
  }
28

29
  // Step 3: we group the positive and negative values
30
  const positives = [];
31
  const negatives = [];
32
  Object.entries(map).forEach((entry) => {
33
    if (entry[1] < 0) negatives.push(entry);
34
    else positives.push(entry);
35
  });
36

37
  // Step 4: backtrack
38
  const numsUsed = new Set();
39
  const backtrack = (val = 0) => {
40
    // if we have used all the characters and the value is 0 the input is solvable
41
    if (!positives.length && !negatives.length) return val === 0;
42

43
    // get the store that we are going to examine depending on the value
44
    let store =
45
      val > 0 || (val === 0 && negatives.length) ? negatives : positives;
46
    if (store.length === 0) return false;
47
    const entry = store.pop();
48
    const [char, multiple] = entry;
49

50
    // try every possible value watching out for the edge case that it was a first character
51
    for (let i = firstChars.has(char) ? 1 : 0; i < 10; i++) {
52
      if (numsUsed.has(i)) continue;
53
      numsUsed.add(i);
54
      if (backtrack(i * multiple + val)) return true;
55
      numsUsed.delete(i);
56
    }
57
    store.push(entry);
58
    return false;
59
  };
60
  return backtrack();
61
};