Sự cố tổng kết hợp sử dụng JavaScript

Giả sử chúng ta được cung cấp một tập hợp các số ứng cử viên (không trùng lặp) và một số mục tiêu (mục tiêu).

Chúng tôi được yêu cầu viết một hàm tìm tất cả các kết hợp duy nhất trong các ứng cử viên mà các số ứng viên cộng lại thành mục tiêu.

Các ứng cử viên có thể chọn cùng một số lặp lại với số lần không giới hạn.

Lưu ý -

• Tất cả các số (bao gồm mục tiêu) sẽ là số nguyên dương.

• Bộ giải pháp không được chứa các kết hợp trùng lặp.

Ví dụ -

Nếu đầu vào là -

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

Giải pháp cho điều này có thể là -

[
   [7],
   [2,2,3]
];

Vì vấn đề là nhận được tất cả các kết quả có thể có, không phải kết quả tốt nhất hoặc số lượng kết quả, do đó chúng tôi không cần xem xét Lập trình động, nên cần có phương pháp bẻ khóa ngược sử dụng đệ quy để xử lý.

Ví dụ

Sau đây là mã -

const recursiveSum = (
   candidates,
   remainingSum,
   finalCombinations = [],
   currentCombination = [],
   startFrom = 0,
) => {
   if (remainingSum < 0) {
      return finalCombinations;
   }
   if (remainingSum === 0) {
      finalCombinations.push(currentCombination.slice());
      return finalCombinations;
   }
   for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) {
      const currentCandidate = candidates[candidateIndex];
      currentCombination.push(currentCandidate);
      recursiveSum(
         candidates,
         remainingSum - currentCandidate,
         finalCombinations,
         currentCombination,
         candidateIndex,
      );
      currentCombination.pop();
   }
   return finalCombinations;
}
const combinationSum = (candidates, target) => recursiveSum(candidates, target);
console.log(combinationSum([2, 3, 6, 7], 7));

Đầu ra

Sau đây là kết quả trên bảng điều khiển -

[ [ 2, 2, 3 ], [ 7 ] ]