Khi giải quyết bài toán Combination Sum II, làm thế nào để xử lý các phần tử trùng lặp trong mảng đầu vào mà không làm sai lệch kết quả cuối cùng?

Question

Accepted Answer

Bản chất vấn đề
Khi mảng đầu vào chứa các số trùng lặp, việc duyệt qua từng phần tử có thể tạo ra các tập hợp con giống hệt nhau. Để tránh điều này, ta cần sắp xếp mảng trước và sử dụng kỹ thuật bỏ qua các phần tử trùng lặp tại cùng một cấp độ đệ quy.
Giải pháp

Sắp xếp mảng đầu vào: nums.sort((a, b) => a - b);
Trong vòng lặp của hàm Backtracking, nếu i > start và nums[i] === nums[i - 1], ta thực hiện continue để bỏ qua nhánh đó.

Ví dụ minh họa
for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue;
  path.push(nums[i]);
  backtrack(i + 1, target - nums[i]);
  path.pop();
}
Lưu ý thực chiến
Việc sắp xếp mảng là bước tiên quyết. Nếu không sắp xếp, ta không thể xác định được các phần tử trùng lặp nằm cạnh nhau để thực hiện cắt tỉa nhánh (Pruning).

Khi giải quyết bài toán Combination Sum II, làm thế nào để xử lý các phần tử trùng lặp trong mảng đầu vào mà không làm sai lệch kết quả cuối cùng?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi backtracking liên quan cùng chủ đề