LC-组合总和

发表于 更新于 分类于

题目描述

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。 

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

代码实现

这里的 sum 函数用来计算一个数组的所有元素之和，backTracking 函数为回溯函数，remain 代表剩余的数组，temp.push(remain[i]); 、backTracking(temp, remain.slice(i)); 、temp.pop(); 是这个函数的核心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let result = [];

  function backTracking(temp, remain) {
    for(let i = 0; i < remain.length; i ++) {
      temp.push(remain[i]);
      if (sum(temp) === target) {
        result.push(temp.slice());
      }
      if (sum(temp) < target) {
        backTracking(temp, remain.slice(i));
      }
      temp.pop();
    }
  }
  backTracking([], candidates);
  return result;
};

function sum(arr) {
  let Sum = 0;
  arr.forEach(ele => {
    Sum += ele;
  });
  return Sum;
}