组合总和

题目详情

题目思路

想的是和求三数之和一样，不断拆分问题，然后使用递归解决 即将目标值变为 target-当前数 然后当 总和等于 target 的时候返回,小于 target 的时候继续递归,大于则跳过（不做处理

• Python 实现

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        res = []
        for i,num in enumerate(candidates):
            if num == target:
                res.append([num])
            elif num < target:
              #如果当前总和小于target,从当前数字后面查找组合,防止出现重复组合
                for r in self.combinationSum(candidates[i:],target-num):
                    res.append([num]+r)
        return res

• TypeScript 实现

function combinationSum(candidates: number[], target: number): number[][] {
  if (candidates.length === 0) return [];
  const res: number[][] = [];
  for (let i = 0; i < candidates.length; i++) {
    if (candidates[i] === target) {
      res.push([candidates[i]]);
    } else if (candidates[i] < target) {
      const subRes = combinationSum(candidates.slice(i), target - candidates[i]);
      subRes.forEach((item) => res.push([candidates[i], ...item]));
    }
  }
  return res;
}

• TypeScript 另一种实现 加入了剪枝的部分，提升了运行速度

function combinationSum(candidates: number[], target: number): number[][] {
  // 排序
  candidates.sort((a, b) => a - b);
  let res = []; // 结果集
  let step = []; // 过程记录

  // 深度优先搜索遍历
  const dfs = (index, target) => {
    if (target == 0) {
      res.push(Array.from(step)); // 记录结果（直接添加 step 为浅拷贝，其结果会随 step 的变化而变化）
      return;
    }

    for (let i = index; i < candidates.length; i++) {
      let tmp = target - candidates[i];
      if (tmp < 0) return; // 剪枝
      else {
        step.push(candidates[i]); // 记录当前步骤
        dfs(i, tmp); // 递归遍历
        step.pop(); // 移除当前步骤
      }
    }
  };

  dfs(0, target);
  return res;
}