[Q&A]-#1

From: sssanXXXX@gmail.com

[Q&A#1] Cho dãy AN = {a1, a2, ..,aN} gồm N số tự nhiên phân biệt. Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) viết chương trình liệt kê tất cả các dãy con K phần tử của dãy số AN (K<=N) sao cho tổng các phần tử của dãy con đó là một số đúng bằng B.

dayso.in	ketqua.out
5 3 50 5 10 15 20 25	2 5 20 25 10 15 25

Quay lui:

/**
 *
 * @author VietAlgo's Blog
 */
#include<bits/stdc++.h>
using namespace std;

#define MAX 9999
int n=0,k=0,b=0;
int countSubArr=0;//Count number array k elements
int A[MAX]={};
int Result[MAX][MAX]={};//Save result sub array k element

void combinationUtil(int arr[], int data[],
					int start, int end,
					int index, int r)
{
	// Current combination is ready
	// to be printed, print it
	if (index == r)
	{
		int sumElement=0;
		//Count sum element in sub array found(combination)
		for (int j = 0; j < r; j++) sumElement+=data[j];
		//Check sum equal B?
		if(sumElement==b){
			//Save result
			for (int j = 0; j < r; j++) Result[countSubArr][j]=data[j];
			countSubArr++;
		}
		return;
	}

	for (int i = start; i <= end && end - i + 1 >= r - index; i++)
	{
		data[index] = arr[i];
		combinationUtil(arr, data, i+1,
						end, index+1, r);
	}
}

void printCombination(int arr[], int n, int r)
{
	// A temporary array to store
	// all combination one by one
	int data[r];

	// Print all combination using
	// temporary array 'data[]'
	combinationUtil(arr, data, 0, n-1, 0, r);
}

int main()
{
	freopen("dayso.in","r",stdin);
	freopen("ketqua.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>k>>b;
	for(int i=0;i<n;i++) cin>>A[i];
	printCombination(A, n, k);
	cout<<countSubArr<<endl;
	for(int i=0;i<countSubArr;i++){
		for(int j=0;j<k;j++) cout<<Result[i][j]<<" ";
		cout<<endl;
	}
}

🥰🥰Mọi người có thể trao đổi, đóng góp ý kiến về ý tưởng hoặc source code dưới bình luận bài viết này nhé. Rất mong nhận được sự chia sẻ của các bạn.