Pattern · 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 không tỉa (pruning) — thử mọi khả năng
// Thực chất backtracking ĐÃ là tối ưu cho bài này;
// "brute force" là thiếu điều kiện dừng sớm (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  // vẫn có điều kiện dừng nhưng không sort trước

    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, trường hợp biên và biến thể công ty Việt Nam.

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 không tỉa (pruning) — thử mọi khả năng // Thực chất backtracking ĐÃ là tối ưu cho bài này; // "brute force" là thiếu điều kiện dừng sớm (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 // vẫn có điều kiện dừng nhưng không sort trước 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 }