Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đếm tập con có tổng cho trước

    Cho một dãy gồm nnn số nguyên dương và một số SSS. Hãy đếm xem có bao nhiêu tập con (có thể rỗng) của dãy mà tổng các phần tử trong tập con đúng bằng SSS.

    Hai tập con được coi là khác nhau nếu chúng khác nhau về tập chỉ số được chọn (kể cả khi các phần tử có giá trị trùng nhau). Hãy dùng đệ quy / quay lui có cắt tỉa để duyệt các khả năng chọn / không chọn từng phần tử.

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên nnn và SSS. Dòng thứ hai chứa nnn số nguyên dương.

    • Ràng buộc đầu vào:

      1≤n≤301 \le n \le 301≤n≤30; 0≤S≤1090 \le S \le 10^90≤S≤109; 1≤ai≤1081 \le a_i \le 10^81≤ai​≤108.

    • Định dạng đầu ra:

      In ra một số nguyên là số tập con có tổng bằng SSS.

    Ví dụ:

    Đầu vào:

    4 5
1 2 3 4

    Đầu ra:

    2

    Giải thích:

    Các tập con có tổng 5: {1,4}, {2,3}. Vậy có 2 tập con.

    Đang tải editor...