Topic describes

Title link:Leetcode-cn.com/problems/co…

Thought analysis

If num is less than target, then target-num is recursively called as the new target. If num is equal to target, the total number is increased by one. At the end of the loop, the total number of combinations under the target is returned.

However, there is a lot of repetition, so you can record the number of combinations for each target and return it the next time you encounter the same target.

code

var combinationSum4 = function (nums, target) {
  let mmap = new Map(a);const recursive = (nums, target) = > {
    let sum = 0;
    if (mmap.has(target)) {
      return mmap.get(target);
    }
    for (num of nums) {
      if (num == target) {
        sum++;
      } else if (num < target) {
        sum += recursive(nums, target - num);
      }
    }
    mmap.set(target, sum);
    return sum;
  }
  recursive(nums, target);
  return mmap.get(target);
};
Copy the code