Tìm Tất Cả Các Tập Con Có Tổng Bằng Một Giá Trị Cho Trước Trong JavaScript

Để tìm tất cả các tập con có tổng bằng một giá trị cho trước trong JavaScript, bạn có thể sử dụng phương pháp đệ quy kết hợp với kỹ thuật backtracking. Phương pháp này sẽ kiểm tra tất cả các tổ hợp có thể của các phần tử trong mảng để tìm ra những tập con có tổng bằng giá trị cho trước.

Mã Nguồn:

function findSubsetsWithSum(nums, targetSum) {
    let result = [];

    function backtrack(start, currentSubset, currentSum) {
        // Kiểm tra nếu tổng hiện tại bằng với targetSum
        if (currentSum === targetSum) {
            result.push([...currentSubset]);
            return;
        }

        // Duyệt qua các phần tử bắt đầu từ vị trí hiện tại
        for (let i = start; i < nums.length; i++) {
            // Thêm phần tử hiện tại vào tập con và cập nhật tổng
            currentSubset.push(nums[i]);
            currentSum += nums[i];

            // Gọi đệ quy để tiếp tục tìm kiếm
            backtrack(i + 1, currentSubset, currentSum);

            // Loại bỏ phần tử cuối cùng để backtrack
            currentSubset.pop();
            currentSum -= nums[i];
        }
    }

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

// Ví dụ kiểm tra
console.log(findSubsetsWithSum([2, 3, 5, 7], 10));
// Output: [[3, 7], [2, 3, 5]]

Giải Thích:

1. Hàm Backtrack:

   • Hàm backtrack được sử dụng để duyệt qua tất cả các tổ hợp của các phần tử trong mảng.
   • Tham số start đại diện cho vị trí bắt đầu của lần duyệt hiện tại.
   • currentSubset là mảng tạm thời lưu trữ các phần tử của tập con hiện tại.
   • currentSum là tổng của các phần tử trong currentSubset.

2. Kiểm Tra Tổng Hiện Tại:

   • Nếu currentSum bằng với targetSum, thêm bản sao của currentSubset vào mảng result.

3. Duyệt Qua Các Phần Tử:

   • Vòng lặp for bắt đầu từ start và duyệt qua tất cả các phần tử còn lại trong mảng nums.
   • Thêm phần tử hiện tại vào currentSubset và cập nhật currentSum.
   • Gọi đệ quy để tiếp tục tìm kiếm từ vị trí tiếp theo (i + 1).
   • Sau khi đệ quy hoàn thành, loại bỏ phần tử cuối cùng khỏi currentSubset và trừ giá trị của nó khỏi currentSum để backtrack và thử các tổ hợp khác.

Tổng Quan:

• Backtracking: Kỹ thuật mạnh mẽ để duyệt qua tất cả các tổ hợp và tìm kiếm tập con có tổng bằng giá trị cho trước.
• Độ Phức Tạp Thời Gian: O(2^n), do có thể có tới 2^n tập con từ một mảng có n phần tử.
• Ứng Dụng: Thích hợp cho các bài toán tổ hợp và tìm kiếm tập con trong các ngôn ngữ lập trình.

Ví Dụ Thực Tế:

console.log(findSubsetsWithSum([2, 3, 5, 7], 10));
// Output: [[3, 7], [2, 3, 5]]
console.log(findSubsetsWithSum([1, 2, 3, 4, 5], 5));
// Output: [[2, 3], [1, 4], [5]]

Trong ví dụ trên, mảng [2, 3, 5, 7] có các tập con [3, 7] và [2, 3, 5] có tổng bằng 10, và mảng [1, 2, 3, 4, 5] có các tập con [2, 3], [1, 4], và [5] có tổng bằng 5.