Backtrack – Live with passion

677

Asif NaeemOctober 25, 2015

#include <iostream>
#include <climits>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

int gr[15][15];
bool found = false;
vector<int> vb;
int node,length;

int backtrack(int st,int len,bool visit[])
{
	if(len==length)
	{
		found=1;
		printf("(");
		for(int i=0;i<vb.size();i++)
		{
			printf("%d%s",vb[i]+1,i==vb.size()-1?")\n":",");
		}
		return 0;
	}
	for(int i=0;i<node;i++)
	{
		if(gr[st][i]==1 && visit[i]==0)
		{
			visit[i]=1;
			vb.push_back(i);
			backtrack(i,len+1,visit);
			visit[i]=0;
			vb.pop_back();
		}
	}
	return 1;
}

int main()
{
	int trash;
	int parent[15];
	bool visit[15];
	bool flag=false;
	do
	{
		scanf("%d",&node);
		scanf("%d",&length);
		memset(gr,0,sizeof(gr));
		for(int i=0;i<node;i++)
		{
			for(int j=0;j<node;j++)
			{
				scanf("%d",&gr[i][j]);
			}
		}
		int len=0;
		int st=0;
		vb.clear();
		for(int i=0;i<node;i++)
		{
			visit[i]=false;
			parent[i]=-1;
		}
		visit[st]=1;
		vb.push_back(st);
		if(flag)
		printf("\n");
		flag=1;
		found=0;
		backtrack(st,len,visit);//from 1st node
		if(!found)
		printf("no walk of length %d\n",length);
	}while(scanf("%d",&trash)==1);
	return 0;
}

#include <iostream>

#include <climits>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

using namespace std;

int gr[15][15];

bool found = false;

vector<int> vb;

int node,length;

int backtrack(int st,int len,bool visit[])

{

if(len==length)

{

found=1;

printf("(");

for(int i=0;i<vb.size();i++)

{

printf("%d%s",vb[i]+1,i==vb.size()-1?")\n":",");

}

return 0;

}

for(int i=0;i<node;i++)

{

if(gr[st][i]==1 && visit[i]==0)

{

visit[i]=1;

vb.push_back(i);

backtrack(i,len+1,visit);

visit[i]=0;

vb.pop_back();

}

return 1;

}

int main()

{

int trash;

int parent[15];

bool visit[15];

bool flag=false;

{

scanf("%d",&node);

scanf("%d",&length);

memset(gr,0,sizeof(gr));

for(int i=0;i<node;i++)

{

for(int j=0;j<node;j++)

{

scanf("%d",&gr[i][j]);

}

int len=0;

int st=0;

vb.clear();

for(int i=0;i<node;i++)

{

visit[i]=false;

parent[i]=-1;

}

visit[st]=1;

vb.push_back(st);

if(flag)

printf("\n");

flag=1;

found=0;

backtrack(st,len,visit);//from 1st node

if(!found)

printf("no walk of length %d\n",length);

}while(scanf("%d",&trash)==1);

return 0;

}

729

Asif NaeemJuly 7, 2015

Using Back Track Algorithm:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;
int N,H;
int backtrack(int idx,int cnt,int a[20])
{
	if(cnt==N-H)
	{
		for(int i=1;i<=N;i++)
			cout<<a[i];
		cout<<"\n";
		return 0;
	}
	for(int i=idx;i<=N;i++)
	{
		a[i]=0;
		backtrack(i+1,cnt+1,a);
		a[i]=1;
	}
	return 0;
}

int main()
{
	int t;
	string s;
	cin>>t;
	getchar();
	getline(cin,s);
	int str[20];
	while(t--)
	{
		cin>>N;
		getchar();
		cin>>H;
		getchar();
		getline(cin,s);
		for(int i=0;i<20;i++)
			str[i]=1;
		backtrack(1,0,str);
		if(t)
		cout<<"\n";

	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

#include <algorithm>

using namespace std;

int N,H;

int backtrack(int idx,int cnt,int a[20])

{

if(cnt==N-H)

{

for(int i=1;i<=N;i++)

cout<<a[i];

cout<<"\n";

return 0;

}

for(int i=idx;i<=N;i++)

{

a[i]=0;

backtrack(i+1,cnt+1,a);

a[i]=1;

}

return 0;

}

int main()

{

int t;

string s;

cin>>t;

getchar();

getline(cin,s);

int str[20];

while(t--)

{

cin>>N;

getchar();

cin>>H;

getchar();

getline(cin,s);

for(int i=0;i<20;i++)

str[i]=1;

backtrack(1,0,str);

if(t)

cout<<"\n";

}

return 0;

}

Using Next_permutation() method in C++

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;
int N,H;

int main()
{
	int t;
	string s;
	cin>>t;
	getchar();
	getline(cin,s);
	int str[20];
	while(t--)
	{
		cin>>N;
		getchar();
		cin>>H;
		getchar();
		getline(cin,s);
		for(int i=0;i<N-H;i++)
			str[i]=0;
		for(int i=N-H;i<N;i++)
			str[i]=1;
		do{
			for(int i=0;i<N;i++)
				cout<<str[i];
			cout<<"\n";
		}
		while(next_permutation(str,str+N));
		if(t)
		cout<<"\n";

	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

#include <algorithm>

using namespace std;

int N,H;

int main()

{

int t;

string s;

cin>>t;

getchar();

getline(cin,s);

int str[20];

while(t--)

{

cin>>N;

getchar();

cin>>H;

getchar();

getline(cin,s);

for(int i=0;i<N-H;i++)

str[i]=0;

for(int i=N-H;i<N;i++)

str[i]=1;

do{

for(int i=0;i<N;i++)

cout<<str[i];

cout<<"\n";

}

while(next_permutation(str,str+N));

if(t)

cout<<"\n";

}

return 0;

}

10364

Asif NaeemFebruary 15, 2015

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define ll long long

using namespace std;

int sz[25];
ll sum;
bool f;
int total_piece;
int stick_size;
bool visit[25];
int M;

bool cmp(int a,int b)
{
	return a>b;
}

bool backtrack(int present_size,int index,int piece_cnt)
{
	if(stick_size*piece_cnt==sum)
		return 1;
	for(int i=index;i<M;i++)
	{
		if(visit[i])
		continue;
		if(i>0 && !visit[i-1] && sz[i]==sz[i-1])
		continue;

		if(present_size+sz[i]==stick_size)
		{
			visit[i]=1;
			if(backtrack(0,0,piece_cnt+1))
			return 1;
			visit[i]=0;
			return 0;
		}
		else if(present_size+sz[i]<stick_size)
		{
			visit[i]=1;
			if(backtrack(present_size+sz[i],i+1,piece_cnt))
			return 1;
			visit[i]=0;
			if(present_size==0)
			return 0;
		}
	}
	return 0;
}

int main()
{
	int t;
	int mx_sz;
	cin>>t;

	while(t--)
	{
		cin>>M;
		mx_sz = 0;
		sum = 0;
		for(int i=0;i<M;i++)
		{
			cin>>sz[i];
			sum+=sz[i];
			if(sz[i]>mx_sz)
				mx_sz = sz[i];
		}
		if(sum%4)
		{
			cout<<"no\n";
			continue;
		}
		if(mx_sz>sum/4)
		{
			cout<<"no\n";
			continue;
		}
		sort(sz,sz+M,cmp);
		memset(visit,0,sizeof(visit));
		stick_size = sum/4;
		if(backtrack(0,0,0))
		cout<<"yes\n";
		else
		cout<<"no\n";
	}

	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

int sz[25];

ll sum;

bool f;

int total_piece;

int stick_size;

bool visit[25];

int M;

bool cmp(int a,int b)

{

return a>b;

}

bool backtrack(int present_size,int index,int piece_cnt)

{

if(stick_size*piece_cnt==sum)

return 1;

for(int i=index;i<M;i++)

{

if(visit[i])

continue;

if(i>0 && !visit[i-1] && sz[i]==sz[i-1])

continue;

if(present_size+sz[i]==stick_size)

{

visit[i]=1;

if(backtrack(0,0,piece_cnt+1))

return 1;

visit[i]=0;

return 0;

}

else if(present_size+sz[i]<stick_size)

{

visit[i]=1;

if(backtrack(present_size+sz[i],i+1,piece_cnt))

return 1;

visit[i]=0;

if(present_size==0)

return 0;

}

return 0;

}

int main()

{

int t;

int mx_sz;

cin>>t;

while(t--)

{

cin>>M;

mx_sz = 0;

sum = 0;

for(int i=0;i<M;i++)

{

cin>>sz[i];

sum+=sz[i];

if(sz[i]>mx_sz)

mx_sz = sz[i];

}

if(sum%4)

{

cout<<"no\n";

continue;

}

if(mx_sz>sum/4)

{

cout<<"no\n";

continue;

}

sort(sz,sz+M,cmp);

memset(visit,0,sizeof(visit));

stick_size = sum/4;

if(backtrack(0,0,0))

cout<<"yes\n";

else

cout<<"no\n";

}

return 0;

}

307

Asif NaeemFebruary 14, 2015

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define ll long long

/*
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
38
2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6
*/

using namespace std;
int sz[101];
ll sum;
bool f;
int total_piece;
int stick_size;
bool visit[101];
int n;

bool cmp(int a,int b)
{
	return a>b;
}

bool backtrack(int present_size,int index,int piece_count)//gainedlength,sticksize,piece count
{
	if(piece_count*stick_size==sum)
		return true;

	for(int i=index;i<n;i++)
	{
		if(visit[i])
			continue;
		if(i>0 && !visit[i-1] && sz[i]==sz[i-1])
			continue;
		if(sz[i]+present_size<stick_size)
		{
			visit[i] = 1;
			f = backtrack(sz[i]+present_size,i+1,piece_count);
			if(f)
			return 1;
			visit[i] = 0;
			if(present_size==0)
			return 0;
		}
		else if(sz[i]+present_size == stick_size)
		{
			visit[i] = 1;
			f = backtrack(0,0,piece_count+1);
			if(f)
			return 1;
			visit[i] = 0;
			return 0;
		}
	}

	return 0;
}

int main()
{
	int max_sz;

	while(cin>>n)
	{
		if(n==0)
		break;
		sum = 0;
		max_sz = 0;
		for(int i=0;i<n;i++)
		{
			cin>>sz[i];
			sum+=sz[i];
			if(sz[i]>max_sz)
			max_sz = sz[i];
		}

		sort(sz,sz+n,cmp);
		bool found = false;
		for(int stk= max_sz;stk<=sum;stk++)
		{
			if(sum%stk)
			continue;
			memset(visit,0,sizeof(visit));
			total_piece = sum/stk;
			stick_size = stk;

			if(backtrack(0,0,0))
			{
				cout<<stk<<"\n";
				found = 1;
				break;
			}
		}
	}

	return 0;
}

100

101

102

103

104

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define ll long long

5 2 1 5 2 1 5 2 1

1 2 3 4

2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6

using namespace std;

int sz[101];

ll sum;

bool f;

int total_piece;

int stick_size;

bool visit[101];

int n;

bool cmp(int a,int b)

{

return a>b;

}

bool backtrack(int present_size,int index,int piece_count)//gainedlength,sticksize,piece count

{

if(piece_count*stick_size==sum)

return true;

for(int i=index;i<n;i++)

{

if(visit[i])

continue;

if(i>0 && !visit[i-1] && sz[i]==sz[i-1])

continue;

if(sz[i]+present_size<stick_size)

{

visit[i] = 1;

f = backtrack(sz[i]+present_size,i+1,piece_count);

if(f)

return 1;

visit[i] = 0;

if(present_size==0)

return 0;

}

else if(sz[i]+present_size == stick_size)

{

visit[i] = 1;

f = backtrack(0,0,piece_count+1);

if(f)

return 1;

visit[i] = 0;

return 0;

}

return 0;

}

int main()

{

int max_sz;

while(cin>>n)

{

if(n==0)

break;

sum = 0;

max_sz = 0;

for(int i=0;i<n;i++)

{

cin>>sz[i];

sum+=sz[i];

if(sz[i]>max_sz)

max_sz = sz[i];

}

sort(sz,sz+n,cmp);

bool found = false;

for(int stk= max_sz;stk<=sum;stk++)

{

if(sum%stk)

continue;

memset(visit,0,sizeof(visit));

total_piece = sum/stk;

stick_size = stk;

if(backtrack(0,0,0))

{

cout<<stk<<"\n";

found = 1;

break;

}

return 0;

}

624

Asif NaeemFebruary 8, 2015

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <cstdio>

#define INF 100000000

using namespace std;

int arr[25];
int res[25];
int SZ;
vector<int> vb;
bool visit[25];
int ind;
int MN;

void backtrack(int remaining,int index)
{

	if(remaining<MN)
	{
		MN = remaining;
		SZ = vb.size();
		for(int i=0;i<SZ;i++)
		{
			res[i] = vb[i];
		}
	}

	for(int i=index+1;i<ind;i++)
	{
		if(visit[i]==0)
		{
			if(remaining - arr[i]<0)
			{
				continue;
			}
			vb.push_back(arr[i]);
			visit[i] = true;
			remaining = remaining - arr[i];
			backtrack(remaining,i);
			visit[i] = false;
			vb.pop_back();
			remaining = remaining + arr[i];
		}

	}

}

int main()
{
	int n,remaining;
	stringstream ss;
	string s;
	for(int i=0;i<25;i++)
		visit[i] = false;

	while(scanf("%d",&arr[0])!=EOF)
	{
		cin>>arr[1];//
		ind=2;//
		for(int i=0;i<arr[1];i++)//
			cin>>arr[ind++];

		remaining = arr[0];
		MN = INF;
		for(int i=2;i<ind;i++)
		{
			if(visit[i]==0)
			{
				if(remaining - arr[i]<0)
				{
					continue;
				}
				visit[i] = true;
				vb.push_back(arr[i]);
				remaining = remaining - arr[i];
				backtrack(remaining,i);
				visit[i] = false;
				remaining = remaining + arr[i];
				vb.pop_back();
			}

		}

		for(int i=0;i<SZ;i++)
			cout<<res[i]<<" ";
		cout<<"sum:"<<arr[0] - MN<<"\n";
	}

	return 0;
}

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

#include <stack>

#include <cstdio>

#define INF 100000000

using namespace std;

int arr[25];

int res[25];

int SZ;

vector<int> vb;

bool visit[25];

int ind;

int MN;

void backtrack(int remaining,int index)

{

if(remaining<MN)

{

MN = remaining;

SZ = vb.size();

for(int i=0;i<SZ;i++)

{

res[i] = vb[i];

}

for(int i=index+1;i<ind;i++)

{

if(visit[i]==0)

{

if(remaining - arr[i]<0)

{

continue;

}

vb.push_back(arr[i]);

visit[i] = true;

remaining = remaining - arr[i];

backtrack(remaining,i);

visit[i] = false;

vb.pop_back();

remaining = remaining + arr[i];

}

int main()

{

int n,remaining;

stringstream ss;

string s;

for(int i=0;i<25;i++)

visit[i] = false;

while(scanf("%d",&arr[0])!=EOF)

{

cin>>arr[1];//

ind=2;//

for(int i=0;i<arr[1];i++)//

cin>>arr[ind++];

remaining = arr[0];

MN = INF;

for(int i=2;i<ind;i++)

{

if(visit[i]==0)

{

if(remaining - arr[i]<0)

{

continue;

}

visit[i] = true;

vb.push_back(arr[i]);

remaining = remaining - arr[i];

backtrack(remaining,i);

visit[i] = false;

remaining = remaining + arr[i];

vb.pop_back();

}

for(int i=0;i<SZ;i++)

cout<<res[i]<<" ";

cout<<"sum:"<<arr[0] - MN<<"\n";

}

return 0;

}

193

Asif NaeemDecember 18, 2014

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int visit[110];
int r[110];
int graph[110][110];
vector<int> vb;
int mx;
int n,k;

int judge(int a)
{
	for(int i=1;i<=n;i++)
	{
		if(graph[a][i])
		{
			if(visit[i]==1 && i!=a)
			return 0;
		}
	}

	return 1;
}

int backtrack(int node)
{
	if(node>n)
	{
		vb.clear();
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(visit[i])
			{
				cnt++;
				vb.push_back(i);
			}
		}
		if(cnt>mx)
		{
			mx=cnt;
			for(int i=0;i<vb.size();i++)
			r[i+1]=vb[i];
		}
	}

	else
	{
		visit[node]=0;
		backtrack(node+1);
		visit[node]=1;
		if(judge(node))
		backtrack(node+1);
		visit[node]=0;
	}
}

int main()
{
	int t,a,b;

	cin>>t;

	while(t--)
	{
		memset(visit,0,sizeof(visit));
		memset(graph,0,sizeof(graph));

		cin>>n>>k;
		for(int i=0;i<k;i++)
		{
			cin>>a>>b;

			graph[a][b]=1;
			graph[b][a]=1;
		}

		mx=0;

		backtrack(1);
		cout<<mx<<"\n";

		for(int i=1;i<=mx;i++)
		cout<<r[i]<<(i!=(mx)?" ":"\n");
	}

	return 0;
}

#include <iostream>

#include <string.h>

#include <vector>

using namespace std;

int visit[110];

int r[110];

int graph[110][110];

vector<int> vb;

int mx;

int n,k;

int judge(int a)

{

for(int i=1;i<=n;i++)

{

if(graph[a][i])

{

if(visit[i]==1 && i!=a)

return 0;

}

return 1;

}

int backtrack(int node)

{

if(node>n)

{

vb.clear();

int cnt=0;

for(int i=1;i<=n;i++)

{

if(visit[i])

{

cnt++;

vb.push_back(i);

}

if(cnt>mx)

{

mx=cnt;

for(int i=0;i<vb.size();i++)

r[i+1]=vb[i];

}

else

{

visit[node]=0;

backtrack(node+1);

visit[node]=1;

if(judge(node))

backtrack(node+1);

visit[node]=0;

}

int main()

{

int t,a,b;

cin>>t;

while(t--)

{

memset(visit,0,sizeof(visit));

memset(graph,0,sizeof(graph));

cin>>n>>k;

for(int i=0;i<k;i++)

{

cin>>a>>b;

graph[a][b]=1;

graph[b][a]=1;

}

mx=0;

backtrack(1);

cout<<mx<<"\n";

for(int i=1;i<=mx;i++)

cout<<r[i]<<(i!=(mx)?" ":"\n");

}

return 0;

}

539

Asif NaeemDecember 8, 2014

Theory: This is an np-hard problem. As the degree of each node can be at most 3 so using dfs ,it can be solved. Follow the link

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

//vector<int> vb[30];
int mat[30][30];
int visit[30];
int n,m;
int length;

void search(int a,int len)
{
	if(len>length)
		length = len;
	for(int i=0;i<n;i++)
	{
		//a=vb[step][i];
		if(mat[a][i]>0)
		{
			mat[a][i]-=1;
			mat[i][a]-=1;
			search(i,len+1);
			mat[a][i]++;
			mat[i][a]++;
		}

	}
}


int main()
{
	int a,b;
	//memset(visit,0,sizeof(visit));
	while(cin>>n>>m)
	{
		if(n==0 && m==0)
		break;

		memset(mat,0,sizeof(mat));
		//for(int i=0;i<n;i++)
		//vb[i].clear();
		length=0;
		for(int i=0;i<m;i++)
		{
			cin>>a>>b;
			//vb[a].push_back(b);
			//vb[b].push_back(a);
			mat[a][b]++;
			mat[b][a]++;
		}

		int len =0;

		for(int i=0;i<n;i++)
		{
			//visit[0]=1;
			search(i,0);
			//visit[0]=0;
		}

		cout<<length<<"\n";
	}
	return 0;
}

#include <iostream>

#include <stdio.h>

#include <vector>

#include <string.h>

using namespace std;

//vector<int> vb[30];

int mat[30][30];

int visit[30];

int n,m;

int length;

void search(int a,int len)

{

if(len>length)

length = len;

for(int i=0;i<n;i++)

{

//a=vb[step][i];

if(mat[a][i]>0)

{

mat[a][i]-=1;

mat[i][a]-=1;

search(i,len+1);

mat[a][i]++;

mat[i][a]++;

}

int main()

{

int a,b;

//memset(visit,0,sizeof(visit));

while(cin>>n>>m)

{

if(n==0 && m==0)

break;

memset(mat,0,sizeof(mat));

//for(int i=0;i<n;i++)

//vb[i].clear();

length=0;

for(int i=0;i<m;i++)

{

cin>>a>>b;

//vb[a].push_back(b);

//vb[b].push_back(a);

mat[a][b]++;

mat[b][a]++;

}

int len =0;

for(int i=0;i<n;i++)

{

//visit[0]=1;

search(i,0);

//visit[0]=0;

}

cout<<length<<"\n";

}

return 0;

}

524

Asif NaeemDecember 6, 2014

#include <iostream>
#include <stdio.h>


using namespace std;


int prime[40]={0,0,2,3,0,5,0,7,0,0,0,11,
                  0,13,0,0,0,17,0,19,0,0,
                  0,23,0,0,0,0,0,29,0,31,0,
                  0,0,0,0,37,0,0};
bool visit[17];
int numbers[17];
int n;

int search(int step)
{
	if(step==n)
	{
		if(prime[1+numbers[step-1]])
		{
			for(int i=0;i<n;i++)
			cout<<numbers[i]<<((i==(n-1))?"\n":" ");
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(prime[numbers[step-1]+i] && !visit[i])
		{
			visit[i]=1;
			numbers[step]=i;
			search(step+1);
			visit[i]=0;
		}
	}
}

int main()
{
	int kase=1;
	int c=0;
	while(cin>>n)
	{
		if(c)
		cout<<"\n";
		c=1;
		cout<<"Case "<<kase++<<":\n";
		numbers[0]=1;
		visit[1]=1;
		search(1);

	}

	return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int prime[40]={0,0,2,3,0,5,0,7,0,0,0,11,

0,13,0,0,0,17,0,19,0,0,

0,23,0,0,0,0,0,29,0,31,0,

0,0,0,0,37,0,0};

bool visit[17];

int numbers[17];

int n;

int search(int step)

{

if(step==n)

{

if(prime[1+numbers[step-1]])

{

for(int i=0;i<n;i++)

cout<<numbers[i]<<((i==(n-1))?"\n":" ");

}

for(int i=1;i<=n;i++)

{

if(prime[numbers[step-1]+i] && !visit[i])

{

visit[i]=1;

numbers[step]=i;

search(step+1);

visit[i]=0;

}

int main()

{

int kase=1;

int c=0;

while(cin>>n)

{

if(c)

cout<<"\n";

c=1;

cout<<"Case "<<kase++<<":\n";

numbers[0]=1;

visit[1]=1;

search(1);

}

return 0;

}

Category: Backtrack

677

729

10364

307

624

193

539

524

Archives

Categories