Giả sử chúng ta được cho một tập hợp các số ứng viên (không trùng lặp) và một số mục tiêu (target).
Chúng ta cần viết một hàm tìm tất cả các tổ hợp duy nhất trong các ứng viên sao cho tổng các số ứng viên bằng mục tiêu.
Cùng một số có thể được chọn từ ứng viên số lượng không giới hạn lần.
Lưu ý:
- Tất cả các số (bao gồm target) đều là số nguyên dương.
- Tập hợp giải pháp không được chứa các 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 có thể là:
[ [7], [2,2,3] ];
Vì bài toán yêu cầu tìm tất cả kết quả có thể, không phải kết quả tối ưu hay số lượng kết quả, nên không cần Quy hoạch động, cần cách tiếp cận backtracking dùng đệ quy.
Ví dụ
Dưới đây là mã nguồn:
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));Kết quả
Đầu ra trên console:
[ [ 2, 2, 3 ], [ 7 ] ]