算法练习07 数字组合总和

发表于 分类于 阅读次数：

给定一个不含重复数字的数组arr，指定个数n，给出目标和sum，判断是否含有由n个不同数字相加得到sum的情况

分析

题目和LeetCode的39题和40题相似，我这个代码自我验证是对的，也不知道是否有问题。

先把《算法图解》入门看完，再刷LeetCode，刷到的时候回来重新看一下吧。

我现在的思路是，基线条件就是n === 1，这个时候的返回条件就是当前循环中的arr[i]与sum是否相等，如果相等就返回true，如果不相等就继续遍历，直到遍历结束，返回false

递归条件是对arr和n和sum同时修改，每次让n不断减少，缩小规模

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function getSum(arr, n, sum) {
  if (arr.length < n) {
    return false
  }
  for (let i = 0; i < arr.length; i++) {
    if (n === 1) {
      if (arr[i] === sum) {
        return true
      }
    } else {
      const result = getSum(arr.slice(i + 1), n - 1, sum - arr[i]);
      if (result) {
        return true
      }
    }
  }
  return false;
}