#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();
Category: Backtrack
729
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
10364
#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] &&
307
#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
624
#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++)
193
#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++;
539
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
524
#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) {