javascript - PlusMinus Challenge - Stack Overflow

admin管理员组

文章数量:1410737

Hi I'm trying to solve this recursion challenge, could anyone give me a hand to plete it please?

This is the challenge:

Have the function PlusMinus(num) read the num parameter being passed which will be a bination of 1 or more single digits, and determine if it's possible to separate the digits with either a plus or minus sign to get the final expression to equal zero. For example: if num is 35132 then it's possible to separate the digits the following way, 3 - 5 + 1 + 3 - 2, and this expression equals zero. Your program should return a string of the signs you used, so for this example your program should return -++-. If it's not possible to get the digit expression to equal zero, return the string not possible. If there are multiple ways to get the final expression to equal zero, choose the one that contains more minus characters. For example: if num is 26712 your program should return -+-- and not +-+-. Sample Test Cases: Input: 199 Output: not possible Input: 26712 Output: -+--

This is what I have tried:

const plusMinus = (num) => {
  let arr = num.toString().split('').map(num => parseInt(num));
  
  return plusMinusRec(arr, 0);

  function plusMinusRec(arr, target){
    if(arr.length == 1){
      if(arr[0] == target){
        return  ""
      } else {
        return "not possible";
      } 
    }

    let s1 = plusMinusRec(arr.slice(1), arr[0]);
    if(s1 != "not possible"){
      return "-" + s1;
    }
    let s2 = plusMinusRec(arr.slice(1), arr[0] * -1);
    if(s2 != "not possible"){
      return "+" + s2;
    }
    return "not possible";
  }  
}

plusMinus(35132);

Hi I'm trying to solve this recursion challenge, could anyone give me a hand to plete it please?

This is the challenge:

Have the function PlusMinus(num) read the num parameter being passed which will be a bination of 1 or more single digits, and determine if it's possible to separate the digits with either a plus or minus sign to get the final expression to equal zero. For example: if num is 35132 then it's possible to separate the digits the following way, 3 - 5 + 1 + 3 - 2, and this expression equals zero. Your program should return a string of the signs you used, so for this example your program should return -++-. If it's not possible to get the digit expression to equal zero, return the string not possible. If there are multiple ways to get the final expression to equal zero, choose the one that contains more minus characters. For example: if num is 26712 your program should return -+-- and not +-+-. Sample Test Cases: Input: 199 Output: not possible Input: 26712 Output: -+--

This is what I have tried:

const plusMinus = (num) => {
  let arr = num.toString().split('').map(num => parseInt(num));
  
  return plusMinusRec(arr, 0);

  function plusMinusRec(arr, target){
    if(arr.length == 1){
      if(arr[0] == target){
        return  ""
      } else {
        return "not possible";
      } 
    }

    let s1 = plusMinusRec(arr.slice(1), arr[0]);
    if(s1 != "not possible"){
      return "-" + s1;
    }
    let s2 = plusMinusRec(arr.slice(1), arr[0] * -1);
    if(s2 != "not possible"){
      return "+" + s2;
    }
    return "not possible";
  }  
}

plusMinus(35132);

• javascript
• algorithm
• recursion

Share Improve this question Follow asked Sep 16, 2019 at 2:48 Mauricio OrozcoMauricio Orozco 7522 silver badges66 bronze badges

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 3

I don't think you're keeping track of the sum as you go deeper into the recursive calls. You either have +arr[0] or -arr[0] as your target for each subsequent recursive call, which does not take into account the sum so far.

But you have have the right idea with this backtracking approach. If you pass in the "sum so far" to each subsequent call, you can check at the end whether the total is 0, and add the plus-minus bination that that path took to your list of possible binations. Finally, you can return the bination with the most minuses.

function PlusMinus(num) {
  let arr = num.split('').map(num => parseInt(num));
  let possibilities = [];

  const traverse = ([d, ...rest], bination, sum) => {
    if (rest.length === 0) {
      if (sum + d === 0) possibilities.push(bination + '+');
      if (sum - d === 0) possibilities.push(bination + '-');
    } else {
      traverse(rest, bination + '+', sum + d);
      traverse(rest, bination + '-', sum - d);
    }
  }

  const maxMinuses = (binations) => {
    return binations.reduce((acc, curr) => [...acc].filter(c => c === '-').length > [...curr].filter(c => c === '-').length ? acc : curr);
  }

  traverse(arr.slice(1), '', arr[0]);
  return possibilities.length ? maxMinuses(possibilities) : 'not possible';
}

console.log(PlusMinus('35132'));
console.log(PlusMinus('199'));
console.log(PlusMinus('26712'));

I improve my code thanks to the advice of the prior answer.

This is the code with the fixes:

const plusMinus = (num) => {
  let arr = num.toString().split('').map(num => parseInt(num));

  if(arr.length < 2){
    return "not possible"
  }

  return plusMinusRec(arr.slice(1), arr[0]);

  function plusMinusRec(arr, sum){
    if(arr.length == 1){
      if(sum + arr[0] === 0){
        return "+";
      } else if(sum - arr[0] === 0){
        return "-";
      } else {
      return "not possible";
    }
  }    

  let s2 = plusMinusRec(arr.slice(1), sum - arr[0]);
  if(s2 != "not possible"){
    return "-" + s2;
  }

  let s1 = plusMinusRec(arr.slice(1), sum + arr[0]);
  if(s1 != "not possible"){
    return "+" + s1;
  }

  return "not possible";
  }  
}

plusMinus(35132);

本文标签： javascriptPlusMinus ChallengeStack Overflow