Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên và một số N. Nhiệm vụ của chúng ta là đếm tổng số cách N có thể được tạo ra bằng cách thêm các phần tử của mảng. Tất cả các kết hợp và lặp lại đều được phép.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr = {1, 3, 5} N = 6 Đầu ra
8
Giải thích
Các cách là -
5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1
Để giải quyết vấn đề này, chúng ta cần sử dụng một cách tiếp cận khác vì tất cả các kiểu kết hợp sẽ được xử lý khác nhau, do đó, nếu số là tổng của 4 phần tử của mảng 4 cách khác nhau được coi là (như trong ví dụ). Để giải quyết một vấn đề như vậy, chúng ta cần sử dụng phương pháp lập trình động và chương trình dưới đây sẽ hiển thị cách triển khai.
Ví dụ
#include <iostream>
#include <cstring>
using namespace std;
int arraySumWays(int array[], int size, int N){
int count[N + 1];
memset(count, 0, sizeof(count));
count[0] = 1;
for (int i = 1; i <= N; i++)
for (int j = 0; j < size; j++)
if (i >= array[j])
count[i] += count[i - array[j]];
return count[N];
}
int main() {
int array[] = {1, 5, 6};
int size = sizeof(array) / sizeof(array[0]);
int N = 7;
cout<<"Total number of ways inwhich "<<N<<" can be generated using sum of elements of array is " <<arraySumWays(array, size, N);
return 0;
} Đầu ra
Total number of ways inwhich 7 can be generated using sum of elements of array is 6