Chủ đề · Quay luiTrung bình ~30 phút đọc + làm

Tổ Hợp Đạt Tổng Mục TiêuCombination Sum

Hiểu bài

Cho mảng số nguyên dương phân biệt candidates và số nguyên target. Tìm tất cả tổ hợp (không trùng nhau) mà tổng bằng target. Mỗi số trong candidates có thể dùng nhiều lần (không giới hạn số lần).

Ví dụ:

candidates = [2, 3, 6, 7], target = 7
output = [[2,2,3], [7]]

candidates = [2, 3, 5], target = 8
output = [[2,2,2,2], [2,3,3], [3,5]]

Điểm mấu chốt: vì mỗi số dùng được nhiều lần, khi đệ quy không tăng start (ở lại index hiện tại).

Khi nhảy sang số tiếp theo mới tăng start — tránh sinh tổ hợp trùng theo thứ tự khác.

Cách cơ bảnO(n^(T/M)) time — n số trong candidates, T là target, M là giá trị nhỏ nhất

// Backtracking without pruning — tries every possibility
// Backtracking is already optimal for this problem;
// the "brute force" here just lacks early termination:
function combinationSumNoPrune(
  candidates: number[],
  target: number
): number[][] {
  const result: number[][] = []

  function backtrack(start: number, current: number[], remaining: number) {
    if (remaining === 0) {
      result.push([...current])
      return
    }
    if (remaining < 0) return  // still has a stop condition, but no sort beforehand

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i])
      backtrack(i, current, remaining - candidates[i])
      current.pop()
    }
  }

  backtrack(0, [], target)
  return result
}

Vì sao cách này chậm:

Không sort candidates → không thể tỉa sớm khi candidates[i] > remaining.

Sort + break khi vượt target giảm đáng kể số nhánh thừa.

Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan

Xem đầy đủ chạy thử từng bước, Big-O và trường hợp biên.

Mở khoá Pro Xem Lifetime

Hiểu bài

Ví dụ:

candidates = [2, 3, 6, 7], target = 7
output = [[2,2,3], [7]]

candidates = [2, 3, 5], target = 8
output = [[2,2,2,2], [2,3,3], [3,5]]

Điểm mấu chốt: vì mỗi số dùng được nhiều lần, khi đệ quy không tăng start (ở lại index hiện tại).

Khi nhảy sang số tiếp theo mới tăng start — tránh sinh tổ hợp trùng theo thứ tự khác.

// Backtracking without pruning — tries every possibility // Backtracking is already optimal for this problem; // the "brute force" here just lacks early termination: function combinationSumNoPrune( candidates: number[], target: number ): number[][] { const result: number[][] = [] function backtrack(start: number, current: number[], remaining: number) { if (remaining === 0) { result.push([...current]) return } if (remaining < 0) return // still has a stop condition, but no sort beforehand for (let i = start; i < candidates.length; i++) { current.push(candidates[i]) backtrack(i, current, remaining - candidates[i]) current.pop() } } backtrack(0, [], target) return result }