Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Learning dynamic programming problems recently, and have such problems, in an array to identify one or a few number, the number can be repeated selection, the selected number of sum to get a number, we want to this problem we can break it down for Jane to difficult, first to see whether there is such a combination in the array, actually such combinations may have multiple, If there is such a set of numbers summed as the target data, we further find such a set of numbers, and finally what we need to do is to choose one of the numbers combined with the least number into the target number.

Whether there is a set of numbers summed to the target number

const canSum = (targetNumber,numbers) = > {
    if(targetNumber === 0 ) return true;
    if(targetNumber < 0) return false;
    for(let num of numbers){
        const reminder = targetNumber - num
        if(canSum(reminder,numbers) === true) {return true}}return false
}
Copy the code
  • First we design the function, and then we don’t have to think too much about it, just the input of the function which is the parameters and the return value of the function.canSumThe function accepts the target valuetargetNumberAnd an array in which you can find a set of numbersnumberThe return value is a Boolean indicating the possibility of such a set of numbers
  • Then we need to consider the subproblem, if the target number is subtracted from some number in the array, if the remaining values can be combined by one or more repeatable arrays in the array, then there is a sum of numbers that can represent the target number.
  • I’m going to set the boundary conditionsif(targetNumber === 0 ) return true;If the target function is 0, it’s found, and if it’s negative, it’s not found
  • Use this statement to transform the problemconst reminder = targetNumber - num

Reduce time complexity through caching

Memoization is used here to optimize to avoid double-counting. Before optimization, let’s look at m = target number size, n represents array length, If the array is all one then the height of the building tree is m and every time you try to branch it is N so it’s m n times O(nm)O(n^m)O(nm) O(m)O(m)O(m), After optimization, the time complexity becomes O(m×n)O(m \times n)O(m×n)


const canSumWithMemo = (targetNumber,numbers,memo={}) => {
    if(targetNumber in memo) return memo[targetNumber];

    if(targetNumber === 0 ) return true;
    if(targetNumber < 0) return false;
    for(let num of numbers){
        const reminder = targetNumber - num
        if(canSum(reminder,numbers) === true){
            memo[targetNumber] = true;
            return true
        }
    }
    memo[targetNumber] = false;
    return false
}

const res = canSumWithMemo(300,[7,14]);
console.log(res)
Copy the code