Bài 13.4. Kho Báu Bị Nguyền Rủa - [Độ khó: Khá]

Bạn lạc vào một căn phòng cổ xưa chứa Kho Báu Bị Nguyền Rủa. Trong đó có N viên đá quý, mỗi viên có một giá trị sức mạnh nhất định. Lời nguyền chỉ được phá giải nếu bạn có thể chọn ra một tập hợp (có thể là rỗng) các viên đá quý sao cho tổng giá trị sức mạnh của chúng chính xác bằng một con số S bí ẩn. Nếu tìm được, bạn sẽ thoát ra an toàn. Nếu không, bạn sẽ bị mắc kẹt vĩnh viễn. Hãy viết một chương trình đệ quy để giúp bạn quyết định liệu có thể thoát khỏi căn phòng hay không.

INPUT FORMAT

• Dòng đầu tiên chứa hai số nguyên N và S, lần lượt là số lượng viên đá quý và tổng giá trị cần tìm.
  • 1 <= N <= 20
  • 0 <= S <= 10^9
• Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N, là giá trị sức mạnh của các viên đá quý.
  • 1 <= a_i <= 10^9

OUTPUT FORMAT

In ra "YES" nếu có thể chọn được một tập hợp các viên đá quý có tổng bằng S, và "NO" nếu không.

Ví dụ:

Input:

4 7
2 3 5 8

Output:

YES

Giải thích:

• Có thể chọn viên đá giá trị 2 và viên đá giá trị 5 để có tổng là 2 + 5 = 7. Vì vậy, câu trả lời là "YES".

Input:

3 10
1 2 3

Output:

NO

Giải thích:

• Từ các viên đá có giá trị {1, 2, 3}, không thể tạo ra tổng bằng 10.
  • Các tổng có thể tạo ra: 0 (tập rỗng), 1, 2, 3, 1+2=3, 1+3=4, 2+3=5, 1+2+3=6. Không có 10.
• Phương pháp đệ quy:
  • Định nghĩa hàm canReachSum(index, currentSum): kiểm tra xem có thể đạt được tổng S từ currentSum bằng cách sử dụng các viên đá từ index trở đi hay không.
  • Điều kiện dừng:
    • Nếu currentSum == S, trả về true.
    • Nếu index == N (đã duyệt hết các viên đá) hoặc currentSum > S (nếu chỉ được cộng các số dương và tổng đã vượt quá S), trả về false.
  • Điều kiện đệ quy:
    • Có hai lựa chọn cho viên đá a[index]:
      1. Chọn a[index]: canReachSum(index + 1, currentSum + a[index])
      2. Không chọn a[index]: canReachSum(index + 1, currentSum)
    • Hàm trả về true nếu ít nhất một trong hai lựa chọn trên trả về true.