Backtracking algorithm tutorial with Example

backtracking Zinnatul Islam Morol Saturday, December 08, 2018

Problem number 1:

Print k numbers in total N numbers. Using Backtracking

Solution:

Input:

Array Size:
5
Array Elements:
1 2 3 4 5

Print how many numbers in this array.

Example input :
2

Then we show this output:

1 2, 1 3, 1 4, 1 5, 2 1, 2 3, 2 4, 2 5, 3 1, 3 2, 3 4, 3 5, 4 1, 4 2, 4 3, 4 5, 5 1, 5 2, 5 3, 5 4

We show print 20 ways in 2 numbers of 5 elements array.

Code:

	#include<bits/stdc++.h>

	using namespace std;

	/// Typedef
	typedef long long ll;

	#define sc1(a) scanf("%lld",&a)
	#define sc2(a,b) scanf("%lld %lld",&a,&b)

	#define pf1(a) printf("%lld\n",a)
	#define pf2(a,b) printf("%lld %lld\n",a,b)

	ll arr[10], newarray[10], num, hownumberprintInALLNumber;
	bool used[10];

	void BT(ll printnum, ll position)
	{
	if(printnum == hownumberprintInALLNumber){
	for(ll i = 0; i < hownumberprintInALLNumber; i++){
	cout << newarray[i];
	}
	cout << endl;
	return;
	}

	for(ll i = 0; i < num; i++){
	if(!used[i]){
	used[i] = true;
	newarray[position] = arr[i];
	BT(printnum+1, position+1);
	used[i] = false;
	}
	}

	}

	int main() {

	ll tc, t = 1;

	//freopen("C:\\Users\\morol\\Desktop\\Clion\\input.txt", "r", stdin);

	cout << "First input array size and Second input How many number print in this" << endl;

	sc2(num, hownumberprintInALLNumber);
	arr[num];

	for(ll i = 0; i < num; i++)
	sc1(arr[i]);

	BT(0, 0);

	return 0;
	}