/* 1a.

Create a Java class called Student with the following details as

variables within it.
(i) USN
(ii) Name
(iii) Branch
(iv) Phone
Write a Java program to create nStudent objects and print the USN, Name, Branch,
and Phone of these objects with suitable headings.
*/

import java.util.Scanner;

class Student {

String USN, Name, Branch, Phone;

Student(String U,String N,String B,String P){
USN=U;
Name=N;
Branch=B;
Phone=P;
}
void display() {
System.out.println( USN+"\t"+Name+"\t"+Branch+"\t"+Phone+"\t");
System.out.println("----------");
}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.println("Enter number of student details to be created");
int n = in.nextInt();

Student[] s = new Student[n];

// Read student details into array of student objects

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

System.out.println("Enter details of student ");
System.out.println("Enter the usn: ");
String usn = in.next();
System.out.println("Enter the name: ");
String name = in.next();
System.out.println("Enter the branch: ");
String branch = in.next();
System.out.println("Enter the phoneno: ");
String phone = in.next();
s[i] = new Student(usn, name, branch, phone);

}System.out.println("USN\tName\tBranch\tPhoneno");
for (int i = 0; i < n; i++) {
s[i].display();
}
}
}

/* 1b. Write a Java program to implement the Stack using arrays. Write Push(),
Pop(), and Display() methods to demonstrate its working.
*/
import java.util.Scanner;
class arrayStack
{
int arr[];
int top, max;

arrayStack(int size){
max = size;
arr = new int[size];
top = -1;
}

void push(int i) {
if (top == max - 1)
System.out.println("Stack Overflow");
else
arr[++top] = i;
}

void pop() {
if (top == -1) {
System.out.println("Stack Underflow");
} else {
int element = arr[top--];
System.out.println("Popped Element: " + element);
}
}

void display() {
System.out.print("\nStack = ");
if (top == -1) {
System.out.print("Empty\n");
return;
}
for (int i = top; i >= 0; i--)
System.out.print(arr[i] + " ");
System.out.println();
}
}

class Stack {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter Size of Integer Stack ");
int n = scan.nextInt();

arrayStack stk = new arrayStack(n);

char ch;
for(;;)
{
System.out.println("\nStack Operations");
 System.out.println("1. push");
System.out.println("2. pop");
System.out.println("3. display");
System.out.println("4. Exit");

int choice = scan.nextInt();

switch (choice) {
case 1:
System.out.println("Enter integer element to push");
stk.push(scan.nextInt());
break;

case 2:
stk.pop();
break;

case 3:
stk.display();
break;

case 4:
System.exit(0);
break;

default:
System.out.println("Wrong Entry \n ");
break;

}
}
}

/* 2a. Design a super class called Staff with details as StaffId, Name, Phone,
Salary. Extend this class by writing three subclasses namely Teaching (domain,
publications), Technical (skills), and Contract (period). Write a Java program
to read and display at least 3 staff objects of all three categories.
*/

import java.util.Scanner;

class Staff {
String StaffID, Name, Phone, Salary;

Scanner input = new Scanner(System.in);

void read() {
System.out.println("Enter StaffID");
StaffID = input.nextLine();

System.out.println("Enter Name");
 Name = input.nextLine();

System.out.println("Enter Phone");
Phone = input.nextLine();

System.out.println("Enter Salary");
Salary = input.nextLine();
}

void display() {

System.out.print("StaffId"+StaffID+"\tName"+Name+"\tPhoneno"+Phone+"\tSalary"+Sa
lary);
}
}

class Teaching extends Staff {

String Domain, Publication;

void read_Teaching() {
super.read(); // call super class read method
System.out.println("Enter Domain");
Domain = input.nextLine();
System.out.println("Enter Publication");
Publication = input.nextLine();
}

void display_Teach() {
super.display(); // call super class display() method
System.out.print("\tDomain"+Domain+"\tPublication"+Publication);
}
}

class Technical extends Staff {

String Skills;

void read_Technical() {
super.read(); // call super class read method
System.out.println("Enter Skills");
Skills = input.nextLine();
}

void display_Tech() {
super.display(); // call super class display() method
System.out.print("\tSkills"+Skills);
}
}

class Contract extends Staff {

String Period;

void read_Contract() {
super.read(); // call super class read method
System.out.println("Enter Period");
Period = input.nextLine();
}

void display_Con() {
super.display(); // call super class display() method
System.out.println("\tPeriod"+Period);
}
}

class Staffdetails {
public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.println("Enter number of staff details to be created");

int n = input.nextInt();

Teaching steach[] = new Teaching[n];

Technical stech[] = new Technical[n];
Contract scon[] = new Contract[n];

// Read Staff information under 3 categories

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

System.out.println("Enter Teaching staff information");
steach[i] = new Teaching();
steach[i].read_Teaching();
}

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

System.out.println("Enter Technical staff information");
stech[i] = new Technical();
stech[i].read_Technical();
}

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

System.out.println("Enter Contract staff information");

scon[i] = new Contract();
scon[i].read_Contract();
}

// Display Staff Information

System.out.println("\n STAFF DETAILS: \n");
System.out.println("-----TEACHING STAFF DETAILS----- ");

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

steach[i].display_Teach();
}

System.out.println();
System.out.println("-----TECHNICAL STAFF DETAILS-----");
for (int i = 0; i < n; i++) {
stech[i].display_Tech();
}

System.out.println();
System.out.println("-----CONTRACT STAFF DETAILS-----");
for (int i = 0; i < n; i++) {
scon[i].display_Con();
}
}
}
import java.util.StringTokenizer;
import java.util.Scanner;

class Customer {
String Name;
String DOB;
public Customer(String n, String d)
{
 Name=n;
DOB=d;
}
public String toString()
{
String returnValue=Name;
StringTokenizer tokenizer= new StringTokenizer(DOB,"/");
System.out.println("The Customer details are ");
while(tokenizer.hasMoreTokens())
{
returnValue=returnValue+","+tokenizer.nextToken();
}
return returnValue;
}
void print(){
System.out.println(toString());
}
public static void main(String[] args) {
Scanner scanner= new Scanner(System.in);
System.out.println("Enter customer name");
String n=scanner.next();
System.out.println("Enter Date (dd/mm/yyyy)");
String d=scanner.next();
Customer a= new Customer(n,d);
a.print();
}
}

/*3a Exception */

import java.util.Scanner;
class Exception3A {

public static void main(String[] args){

int a,b,c;
Scanner in = new Scanner(System.in);
System.out.println("Enter the value of a: ");
a= in.nextInt();
System.out.println("Enter the value of b: ");
b=in.nextInt();
try{
c=a/b;
System.out.println("the result is "+ c);
}
catch(ArithmeticException e){
System.out.println(e);
}
}
}

/*
Write a Java program that implements a multi-thread application that has three
threads.
First thread generates a random integer for every 1 second; second thread
computes the
square of the number and prints; third thread will print the value of cube of
the number.
*/
import java.util.Random;

class SquareThread implements Runnable {

int x;

SquareThread(int x) {
this.x = x;
}

public void run() {

System.out.println("Thread Name:Square Thread and Square of " + x + "
is: " + x * x);
}
}

class CubeThread implements Runnable {

int x;

CubeThread(int x) {
this.x = x;
}

public void run() {

System.out.println("Thread Name:Cube Thread and Cube of " + x + " is: "
+ x * x * x);
}
}

class RandomThread implements Runnable {

Thread t2, t3;

public void run() {

int num;
Random r = new Random();
try {

for(int i=1;i<=3;i++) {
num = r.nextInt(10);
System.out.println("Main Thread and Generated Number is " +
num);
t2 = new Thread(new SquareThread(num));
t2.start();

t3 = new Thread(new CubeThread(num));

t3.start();

Thread.sleep(1000);
System.out.println("--------------------------------------");
}
} catch (Exception ex) {
System.out.println("Interrupted Exception");
}
}
}

public class Multithread {

public static void main(String[] args) {

RandomThread thread_obj = new RandomThread();

Thread t1 = new Thread(thread_obj);
t1.start();
}
}
import java.util.Scanner;
import java.util.Random;
public class Quick_sort {
int a[];
int n;

Quick_sort(int size)
{
n=size;
a=new int[n+1];
a[n]=101;
}
void read(){
Random rd=new Random();
System.out.println("array elements: ");
for(int i=0;i<n;i++){
a[i]=rd.nextInt(100);
}
}
void display() {
System.out.println("sorted elements are : ");
for (int i = 0; i < n; i++) {
System.out.println(a[i]);
}
}
void quicksort(int low,int high){
if(low<high){
int j=partition(low,high);
quicksort(low,j-1);
quicksort(j+1,high);
}
}
int partition(int low,int high){
int i=low;int j=high+1;
int pivot=a[low];
while(i<j){
do{
i++;
}while(pivot>=a[i]);
do{
j--;
}while(pivot<a[j]);
if(i<j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
int temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
System.out.println("Enter the no of elements: ");
int n=in.nextInt();
Quick_sort a=new Quick_sort(n);
a.read();
a.display();
long start=System.nanoTime();
a.quicksort(0,n-1);
long end=System.nanoTime();
 a.display();
long start1=System.nanoTime();
a.display();
long end1=System.nanoTime();
System.out.println("Time complexity is "+(end-start)+"ns");
System.out.println("time after sorted: "+(end1-start1)+"ns");
}
}

/*5 Mergesort */

import java.util.Scanner;
//import java.util.Random;
class Merge_sort {
int a[];
int n;

Merge_sort(int size){
n=size;
a= new int[size];
}
void read(){
Scanner in = new Scanner(System.in);
System.out.println("Enter the array elements: ");
for(int i=0;i<n;i++){
a[i]=in.nextInt();
}
}
void display(){
System.out.println("The array elements are: ");
for(int i=0;i<n;i++){
System.out.print(a[i]);
}
}
void mergesort(int low,int high){
int mid;
if(low<high){
mid=low+high/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low, int mid,int high){

int i=low; int j=mid+1; int k=low;

int c[]=new int[high+1];
while(i<=mid && j<=high){
if(a[i]<a[j]){
c[k]=a[i];
 i++;
k++;
}
else{
c[k]=a[j];
j++;
k++;
}
}
while(i<=mid){
c[k]=a[i];
i++;
k++;
}
while(j<=high){
c[k]=a[j];
j++;
k++;
}
for(k=low;k<=n;k++){
a[k]=c[k];
}
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.println("Enter the no of elements: ");
int n=in.nextInt();
Merge_sort a= new Merge_sort(n);
a.read();
a.display();
long start = System.nanoTime();
a.mergesort(0,n-1);
long end = System.nanoTime();
a.display();
System.out.println("Time complexity is "+(end-start)+"ns");
}
}

*6a knapsack dynamic */

import java.util.Scanner;
public class DynamicKnapsack {
int n,m,p[],w[],v[][],x[];

DynamicKnapsack(int size,int max) {

n=size;
m=max;
w = new int[n + 1];
v = new int[n + 1][max + 1];
 p = new int[n + 1];
x=new int[n+1];
}
void read(){
Scanner in = new Scanner(System.in);
System.out.println("Enter the weights in decreasing order of v/w: ");
for(int i=1; i<=n;i++)
w[i]=in.nextInt();

System.out.println("Enter the profit in decreasing order of v/m: ");

for(int i=1;i<=n;i++)
p[i]=in.nextInt();
}

void knap()
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
if(i==0||j==0)
v[i][j] = 0;
else if (w[i] > j)
v[i][j] = v[i - 1][j];

else {
if((v[i - 1][j])>(v[i-1][j-w[i]]+p[i]))
v[i][j]=v[i-1][j];

else
v[i][j] = v[i - 1][j - w[i]] + p[i];
}
}
}
int j=m;
for(int i=1;i<=n;i++)
{
if(v[i][j]==v[i-1][j])
x[i]=0;
else
{
x[i]=1;
j=j-w[i];
}
}
}

void display(){
System.out.println("profit is "+v[n][m]);
for(int i=1;i<=n;i++)
System.out.println(x[i]+"\t");
System.out.println();
}
public static void main(String[] args){
Scanner in =new Scanner(System.in);
System.out.println("Enter no item :");
int num=in.nextInt();
System.out.println("Enter capacity: ");
int max=in.nextInt();
DynamicKnapsack a=new DynamicKnapsack(num,max);
a.read();
a.knap();
a.display();
 }
}

/*6b Greedy knapsack */

import java.util.Scanner;
class KnapsackB{
int N;
int sum=0;
int M;
int w[];
int p[];
int x[];
KnapsackB(int n){
N=n+1;
p=new int[n+1];
w=new int[n+1];
x=new int[n+1];
}
void knap()
{
int Rc=M;
for(int i=1;i<N;i++){
x[i]=0;
}
for(int i=1;i<N;i++){
if(w[i]<=Rc)
{
x[i]=1;
Rc=Rc-w[i];
}
}

}
void read()
{
Scanner in = new Scanner(System.in);
System.out.println("Enter the maximaum capacity: ");
M=in.nextInt();
System.out.println("Enter the profit of each object:");
for(int i=1;i<N;i++)
{
p[i]=in.nextInt();
}
System.out.println("Enter the weights: ");
for(int i=1;i<N;i++)
{
w[i]=in.nextInt();
}
 }
void display(){
System.out.println("The profit is : ");
for(int i=1; i<N;i++){
sum=sum+p[i]*x[i];
}
System.out.println(sum);
System.out.println("solution vector is : ");
for(int i=1;i<N;i++){
System.out.println(x[i]);
}
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in) ;
System.out.println("Enter the no elements: ");
int N = in.nextInt();
KnapsackB a = new KnapsackB(N);
a.read();
a.knap();
a.display();

/*7 DJ */

import java.util.Scanner;
class Shorteshpath {
int visited[];
int source;
int cost[][];
int near[];
int n;
int u=0,v=0;
int d[];

Shorteshpath(int size){
n=size;
near=new int[n+1];
visited=new int[n+1];
cost=new int[n+1][n+1];
d=new int[n+1];
}
void read(){
try (Scanner in = new Scanner(System.in)) {
System.out.println("Enter the source vertex: ");
 source = in.nextInt();
System.out.println("Enter the cost adj matrix: ");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cost[i][j]=in.nextInt();
}
}
}
}
void display(){
for(int v=1;v<=n;v++){
int i=v;
do{
System.out.println(v);
System.out.print("<--");
i=near[i];
}while(i!=source);{
System.out.println(source+"\t cost is "+d[v]);

}
}
}
void dijktra(){
int i;
for(i=1;i<=n;i++){
d[i]=cost[source][i];
near[i]=source;
visited[i]=0;
}
visited[source]=1;
for(int k=1;k<=n-2;k++){
int min=9999;
for(i=1;i<=n;i++){
if(visited[i]==0 && d[i]<min){
min=d[i];
u=i;
}
}

visited[u]=1;
for(int v=1;v<=n;v++)
{

if(visited[v]== 0 && d[u]+cost[u][v] < d[v])

{
d[v]=d[u]+cost[u][v];
near[v]=u;
}
}
}
}
 public static void main(String[] args){
try (Scanner in = new Scanner(System.in)) {
System.out.println("Enter the size of matrix: ");
int n=in.nextInt();
Shorteshpath a= new Shorteshpath(n);
a.read();
a.dijktra();
a.display();
}
}
}

/* 8 Krushkals */

import java.util.Scanner;
public class Kruskal{
int n,cost[][],u,v,mincost,parent[];
Kruskal(int size){
n=size;
cost = new int[n+1][n+1];
parent=new int[n+1];
}
void read(){
Scanner in =new Scanner(System.in);
System.out.println("enter cost matrix: ");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cost[i][j] = in.nextInt();
}
}
for(int i=1;i<=n;i++)
parent[i]=-1;

}
void kruskal(){
int ne=1;
while(ne<n)
{
int min=999;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(min>cost[i][j])
{
min=cost[i][j];
u=i;v=j;
}
}
}
if(min==999){
System.out.println("No spanning tree");
System.exit(0);
}
int a=find(u);
 int b=find(v);
if(a!=b)
{
ne=ne+1;
System.out.println(u+"-->"+v);
mincost=mincost+cost[u][v];
union(a,b);
}
cost[u][v]=cost[v][u]=999;
}
System.out.println("minimum cost is: "+mincost);
}
void union(int i,int j){
if(i<j)
parent[j]=i;
else
parent[i]=j;
}
int find(int i){
while(parent[i]>=0)
{
i=parent[i];
}
return i;
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
System.out.println("enter size: ");
int n=in.nextInt();
Kruskal a=new Kruskal(n);
a.read();
a.kruskal();
}
}
/*enter size:
7
enter cost matrix:
0 28 999 999 999 10 999
28 0 16 999 999 999 14
999 16 0 12 999 999 999
999 999 12 0 22 999 18
999 999 999 22 0 25 24
10 999 25 999 25 0 999
999 14 24 18 24 999 0
1-->6
3-->4
2-->7
2-->3
4-->5
5-->6
minimum cost is: 99
*/

/* 9 Prims */

import java.util.Scanner;
public class Main {
int cost[][];
int near[];
int n;
int mincost;
int d[];
int t[][];
int v;
Main(int size){
n=size;
cost=new int[n+1][n+1];
near=new int[n+1];
t=new int[n-1][2];
d=new int[n+1];
}
void read(){
Scanner in = new Scanner(System.in);
System.out.println("Enter cost adj matrix: ");
for(int i=1;i<=n;i++){
for(int j=1; j<=n;j++){
cost[i][j]=in.nextInt();
}
}
}
void prims()
{
int min=9999;
int k=0;
int l=0;
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++){
if(cost[i][j]<min){
min=cost[i][j];
k=i;
l=j;
}
}
}
for(int i=1;i<=n;i++)
{
if(cost[i][k] < cost[i][l])
near[i]=k;
else
near[i]=l;
d[i]=cost[i][near[i]];

}
near[k]=near[l]=0;
mincost = cost[k][l];
t[0][0]=k;
t[0][1]=l;
for(int i=1;i<=n-2;i++){
min=9999;
int j=1;
for(int v=1;v<=n;v++){

if(d[v]<min && near[v]!=0){

min=d[v];
j=v;
}
}
t[i][0]=j;
t[i][1]=near[j];
mincost=mincost+d[j];
near[j]=0;
for(int v=1; v<n;v++){
if(near[v]!=0 && d[v]>cost[j][v]){
near[v]=j;
d[v]=cost[v][j];
 }
}
}

}
void print(){
int j=1;
int min=9999;
System.out.println("The edges of Minimum Cost Spanning Tree are:");
for(int i=0;i<=n-2;i++){
System.out.print(t[i][0]+",");
System.out.print(t[i][1]+":"+mincost);
System.out.println();
}
System.out.println("mincost is "+mincost);
}
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
System.out.println("Enter size: ");
int n = in.nextInt();
Main a = new Main(n);
a.read();
a.prims();
a.print();
}
}
/*
0
10
999
30
999
999
10
0
50
999
40
25
999
50
0
999
35
15
30
999
999
0
999
20
999
40
35
999
0
55
999
25
15
20
55
0
*/
/*10b Travelling sales person */
import java.util.Scanner;
public class TravSalesPerson {
static int MAX = 100;
static final int infinity = 999;
public static void main(String args[]) {
int cost = infinity;
int c[][] = new int[MAX][MAX]; // cost matrix
int tour[] = new int[MAX]; // optimal tour
int n; // max. cities
System.out.println("Travelling Salesman Problem using
DynamicProgramming\n");
System.out.println("Enter number of cities: ");
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
System.out.println("Enter Cost matrix:\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
c[i][j] = scanner.nextInt();
if (c[i][j] == 0)
c[i][j] = 999;
}
for (int i = 0; i < n; i++)
tour[i] = i;
cost = tspdp(c, tour, 0, n);
System.out.println("Minimum Tour Cost: " + cost);
System.out.println("\nTour:");
for (int i = 0; i < n; i++) {
System.out.print(tour[i] + " -> ");
}
System.out.println(tour[0] + "\n");
scanner.close();
}
static int tspdp(int c[][], int tour[], int start, int n) {
int i, j, k;
int temp[] = new int[MAX];
int mintour[] = new int[MAX];
int mincost;
int cost;
if (start == n - 2)
return c[tour[n - 2]][tour[n - 1]] + c[tour[n - 1]][0];
mincost = infinity;
for (i = start + 1; i < n; i++) {
for (j = 0; j < n; j++)

temp[j] = tour[j];
temp[start + 1] = tour[i];
temp[i] = tour[start + 1];
if (c[tour[start]][tour[i]] + (cost = tspdp(c, temp, start + 1, n))
<
mincost) {
mincost = c[tour[start]][tour[i]] + cost;
for (k = 0; k < n; k++)
mintour[k] = temp[k];
}}
for (i = 0; i < n; i++)
tour[i] = mintour[i];
return mincost;
}
}
/*10a FLoyd's */

package javapracticeprograms;
import java.util.Scanner;
public class Floyds {
int n,c[][],d[][];
Floyds(int n){
this.n=n;
c=new int[n+1][n+1];
d=new int[n+1][n+1];
}
void floyds()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j] = c[i][j];
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if ((d[i][j]>d[i][k] + d[k][j]) ){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}

void read(){
Scanner in = new Scanner(System.in);
System.out.println("Enter the Cost Matrix (999 for infinity) \n");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
c[i][j] = in.nextInt();
}
}

}
void display(){
System.out.println("The All Pair Shortest Path Matrix is:\n");
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++){
System.out.print(d[i][j]+"\t");

}
System.out.println("\n");
 }
}
public static void main(String[] args){
Scanner in =new Scanner(System.in);
System.out.println("Enter the size of matrix: ");
int n=in.nextInt();
Floyds a = new Floyds(n);
a.read();
a.floyds();
a.display();
}
}
//11.SUMOFSUBSETS

import java.util.Scanner;

class SubSet
{
static int c;
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
System.out.println("Enter no of elements ");
int n=s.nextInt();
int sum=0;
System.out.println("Enter elements ");//Input the elements and calculate
the sum of them
int w[]=new int[n];
for(int i=0;i<n;i++)
{ w[i]=s.nextInt();
sum+=w[i];
}
int x[]=new int[n];

System.out.println("Enter the requried sum : ");

int d= s.nextInt();
c=0;//count var
//calculation of sum,already done in above input loop
//Check if sum is smaller than the requried sum or if the first element
itself is greater than the sum
if(sum<d || w[0]>d)
System.out.println("NO SOLUTION");//then no possible sol exists
else //Else call the function
subset(0,0,sum,x,w,d);
if(c==n-1)//if there is no solution even after all reursions
System.out.println("NO SOLUTION");
}
static void subset(int cs,int k,int r,int x[],int w[],int d)
{
x[k]=1;//Pick k'th element
c++;
//If current sum + next element = requried solution we Print out the
w[i] for which x[i]=1;
if(cs + w[k]==d)
{
System.out.println("Solution");
for(int i=0;i<=k;i++)
{
if(x[i]==1)
System.out.println(w[i]);
 }
}
//If current sum + next-next(k+1)'th element is less than requried sum
then we include the next element(k) and recurse with k+1
else if(cs+w[k]+w[k+1]<=d)
{
subset(cs+w[k],k+1,r-w[k],x,w,d);
}
//If including next element(k) from remaining excedes req sum but the
next-next(k+1)th element can be included not to exceed req sum
if(cs+r-w[k]>=d && cs+w[k+1]<=d)
{
x[k]=0;//Then exculde the selected , next element(k)
subset(cs,k+1,r-w[k],x,w,d);//recurse without adding w[k] to cs
}
}
}
Enter no of elements
5
Enter elements
1 2 3 5 6
Enter the requried sum :
10
Solution
1
3
6
Solution
2
3
5
=======================
Enter no of elements
3
Enter elements
10 20 30
Enter the requried sum :
25
NO SOLUTION
=======================
Enter no of elements
3
Enter elements
20 42 56
Enter the requried sum :
15
NO SOLUTION

/* 12. Hamiltonian cycle */

import java.util.Scanner;

public class Hamiltonian {

int G[][];// = new int[n + 1][n + 1];

int x[];// = new int[n + 1];
int n;
Hamiltonian(int n){
this.n=n;
G = new int[n + 1][n + 1];
x = new int[n + 1];
 x[1]=1;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
System.out.print("\nEnter the size: ");
int n = in.nextInt();
Hamiltonian a= new Hamiltonian(n);
a.read();
System.out.println("\t\t\tHamiltonian Cycle");

System.out.println("\nSolution:");
a.HamiltonianMethod(2);
}

void read() {
Scanner in = new Scanner(System.in);

System.out.print("\nEnter tha adj matrix \n");

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

G[j][i] = G[i][j] = in.nextInt();

}
}
}

void HamiltonianMethod(int k) {
do {
NextValue(k, G, x, n);
if (x[k] == 0)
return;
if (k == n) {
System.out.println("Cycle");
for (int i = 1; i <= k; i++)

System.out.print(x[i] + " ");

System.out.print(1);
System.out.println();
} else{
HamiltonianMethod(k + 1);
}
}while(true);
}

void NextValue(int k, int G[][], int x[], int n) {

while (true) {
x[k] = (x[k] + 1) % (n + 1);
if (x[k] == 0)
return;
if (G[x[k - 1]][x[k]] != 0) {
int j;
for (j = 1; j < k; j++){
if (x[k] == x[j])
break;
}
if (j == k)
if ((k < n) || ((k == n) && G[x[n]][x[1]] != 0)){
return;
}
}
}
}
}
/*
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
*/