TNotes.leetcode

Appearance

0039. 组合总和【中等】

0039. 组合总和【中等】 ​

1. 📝 题目描述 ​

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

txt
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解释：

  • 2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次。
  • 7 也是一个候选， 7 = 7。
  • 仅有这两种组合。

示例 2：

txt
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

txt
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素互不相同
  • 1 <= target <= 40

2. 🎯 s.1 - 回溯 + 排序剪枝 ​

c
int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** g_ans;
int* g_colSizes;
int g_ansSize;
int g_path[40];
int g_pathLen;

void backtrack(int* candidates, int candidatesSize, int start, int remain) {
    if (remain == 0) {
        g_ans[g_ansSize] = (int*)malloc(g_pathLen * sizeof(int));
        memcpy(g_ans[g_ansSize], g_path, g_pathLen * sizeof(int));
        g_colSizes[g_ansSize] = g_pathLen;
        g_ansSize++;
        return;
    }
    for (int i = start; i < candidatesSize; i++) {
        if (candidates[i] > remain)
            break; // 剪枝
        g_path[g_pathLen++] = candidates[i];
        backtrack(candidates, candidatesSize, i, remain - candidates[i]);
        g_pathLen--;
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int** combinationSum(int* candidates, int candidatesSize, int target,
                     int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), compare);
    g_ans = (int**)malloc(300 * sizeof(int*));
    g_colSizes = (int*)malloc(300 * sizeof(int));
    g_ansSize = 0;
    g_pathLen = 0;
    backtrack(candidates, candidatesSize, 0, target);
    *returnSize = g_ansSize;
    *returnColumnSizes = g_colSizes;
    return g_ans;
}
js
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  candidates.sort((a, b) => a - b)
  const ans = []

  const backtrack = (start, remain, path) => {
    if (remain === 0) {
      ans.push([...path])
      return
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) break // 剪枝
      path.push(candidates[i])
      backtrack(i, remain - candidates[i], path) // 可重复选取，下一轮仍从 i 开始
      path.pop()
    }
  }

  backtrack(0, target, [])
  return ans
}
py
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []

        def backtrack(start: int, remain: int, path: List[int]) -> None:
            if remain == 0:
                ans.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remain:
                    break  # 剪枝
                path.append(candidates[i])
                backtrack(i, remain - candidates[i], path)  # 可重复选取
                path.pop()

        backtrack(0, target, [])
        return ans
  • 时间复杂度：O(n⋅2Tm)，其中 T 是目标和，m 是候选数组最小元素，n 是每个结果复制的开销
  • 空间复杂度：O(Tm)，递归栈深度最多为 Tm（不计输出结果）

算法思路：

  • 先对 candidates 升序排序，使枚举有序，便于剪枝
  • backtrack(start, remain, path)：从下标 start 开始枚举，每次选取 candidates[i] 后，下一层仍从 i 开始（允许重复选取）
  • remain == 0 时收集当前路径到结果；若 candidates[i] > remain 则 break（后续元素更大，无需继续）

Discussions