purchaseInShop

Có một cửa hàng bán hàng tự động, có rất nhiều mặt hàng được bán nhưng tất cả các mặt hàng đều có cùng một giá bán là m. Cửa hàng này không có nhân viên bán hàng mà chỉ bán hàng bằng máy, mỗi máy chỉ bán một mặt hàng. Máy bán hàng có một khe để nhận tiền bằng đồng xu và biết được mệnh giá của các đồng xu khi người mua nhét vào đó. Khi muốn mua một mặt hàng nào người mua chọn máy có mặt hàng mình muốn và nhét các đồng xu vào máy qua khe nhận tiền, khi số tiền bỏ vào máy đúng m thì máy sẽ đưa ra một món hàng tương ứng.

Một người mua hàng có dãy các đồng xu, đồng xu thứ i có mệnh giá là ai, người này muốn mua một món hàng nhưng không biết phải chọn các đồng xu mình đang có như thế nào để mua được món hàng đó. Hãy giúp người mua hàng xác định số cách chọn khác nhau để mua một món hàng (hai cách chọn được xem là giống nhau nếu mệnh giá các đồng xu được chọn của hai cách là giống nhau, không xét vị trí i và thứ tự chọn đồng xu, 1+4 và 4+1 là như nhau)

Ví dụ:

• Với a = [1,2,3,4,5,6] và m = 5. Giá của mỗi món hàng là 5 và người mua hàng có 3 cách lựa chọn để mua là: 1+4, 2+3 và 5. Output là purchaseInShop(a,m) = 3.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s (C++), 3s (Java, C#), 4s (Python, JavaScript) 
• [Đầu vào] arr.integer a, integer m

   2 < a.size() ≤ 20

• [Đầu ra] integer

    Số cách chọn khác nhau để mua một món hàng có giá là m.