39.组合总和

链接：39.组合总和
难度：Medium
标签：数组、回溯
简介：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

题解 1 - typescript

• 编辑时间：2020-09-09
• 执行用时：104ms
• 内存消耗：44.9MB
• 编程语言：typescript
• 解法介绍：遍历数组递归。

function combinationSum(candidates: number[], target: number): number[][] {
  const len = candidates.length;
  if (len === 0) return [];
  else if (len === 1) {
    const num = candidates[0];
    return target % num === 0 ? [new Array(target / num).fill(num)] : [];
  }
  const ans: number[][] = [];
  for (let i = 0; i < len; i++) {
    const num = candidates[i];
    let sum = 0;
    let arr = combinationSum([num], target);
    let count = 0;
    if (arr.length !== 0) ans.push(...arr);
    while ((sum += num) < target) {
      count++;
      arr = combinationSum(candidates.slice(i + 1), target - sum);
      arr.length !== 0 && ans.push(...arr.map(v => new Array(count).fill(num).concat(v)));
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-07-25
• 执行用时：92ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：dfs+剪枝，每次遍历时，可以选当前值或者下一值。

function combinationSum(candidates: number[], target: number): number[][] {
  const ans: number[][] = [];
  dfs();
  return ans;
  function dfs(index = 0, value = 0, list: number[] = []) {
    if (value >= target || index === candidates.length) {
      value === target && ans.push([...list]);
      return;
    }
    const candy = candidates[index];
    list.push(candy);
    dfs(index, value + candy, list);
    list.pop();
    dfs(index + 1, value, list);
  }
}

题解 3 - python

• 编辑时间：2024-04-20
• 执行用时：42ms
• 内存消耗：16.42MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(candidates)
        def dfs(index: int, cur: int, arr: List[int]):
            if index == n:
                if cur == target:
                    res.append(arr[:])
            elif cur > target:
                return
            else:
                dfs(index + 1, cur, arr)
                cnt = 1
                while cur + cnt * candidates[index] <=  target:
                    dfs(index + 1, cur + cnt * candidates[index], arr + [candidates[index]] * cnt)
                    cnt += 1
        dfs(0, 0, [])
        return res