public boolean groupSum(int start, int[] nums, int target) {
    // Base case: if there are no numbers left, then there is a
    // solution only if target is 0.
    if (start >= nums.length) return (target == 0);
    
    // Key idea: nums[start] is chosen or it is not.
    // Deal with nums[start], letting recursion
    // deal with all the rest of the array.
    
    // Recursive call trying the case that nums[start] is chosen --
    // subtract it from target in the call.
    if (groupSum(start + 1, nums, target - nums[start])) return true;
    
    // Recursive call trying the case that nums[start] is not chosen.
    if (groupSum(start + 1, nums, target)) return true;
    
    // If neither of the above worked, it's not possible.
    return false;
  }

Backtracking

Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are blocked, means rat can­not enter into those cells. Rat can move in any direc­tion ( left, right, up and down).

Input: A 2D-matrix with 0’s and 1’s fill in it. 0 means that cell is blocked and 1 means rat can move to that cell.

Approach:

Cre­ate a solu­tion matrix of the same struc­ture as maze. When­ever rat moves to cell in a maze, mark that par­tic­u­lar cell in solu­tion matrix. At the end print the solu­tion matrix, fol­low that 1’s from the top left cor­ner, it will be that path for the rat. Algo­rithm:

If rat reaches the des­ti­na­tion print the solu­tion matrix. Else Mark the cur­rent cell in solu­tion matrix as 1 If pre­vi­ous step is not in ver­ti­cal direc­tion (upwards) then move for­ward in the ver­ti­cal direction(downwards) and recur­sively check if this move­ment leads to solution. If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in hor­i­zon­tal direc­tion (towards left) then move for­ward in the hor­i­zon­tal direction(towards right) and recur­sively check if this move­ment leads to solution. If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in ver­ti­cal direc­tion (down­wards) then move for­ward in the hor­i­zon­tal direction(upwards) and recur­sively check if this move­ment leads to solution. If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in hor­i­zon­tal direc­tion (towards right) then move for­ward in the hor­i­zon­tal direction(towards left) and recur­sively check if this move­ment leads to solution. If none of the above solu­tion works then BACKTRACK and mark the cur­rent cell as 0. NOTE: It is impor­tant to check the pre­vi­ous direc­tion in which the rat has moved because if rat will move in the oppo­site direc­tion w.r.t its pre­vi­ous direc­tion then rat might end up in infi­nite loop. Exam­ple: if rat has moved to its left in the pre­vi­ous direc­tion then if in next moves to right then mov­ing left option will be avail­able again then rat will move to left again , then again right and so on

    public class RatInMaze {

public int[][] solution;

//initialize the solution matrix in constructor.
public RatInMaze(int N) {
	solution = new int[N][N];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			solution[i][j] = 0;
		}
	}
}

public void solveMaze(int[][] maze, int N) {
	if (findPath(maze, 0, 0, N, "down")) {
		print(solution, N);
	}else{
		System.out.println("NO PATH FOUND");
	}
	
}

public boolean findPath(int[][] maze, int x, int y, int N, String direction) {
	// check if maze[x][y] is feasible to move
	if(x==N-1 && y==N-1){//we have reached
		solution[x][y] = 1;
		return true;
	}
	if (isSafeToGo(maze, x, y, N)) {
		// move to maze[x][y]
		solution[x][y] = 1;			
		// now rat has four options, either go right OR go down or left or go up
		if(direction!="up" && findPath(maze, x+1, y, N, "down")){ //go down
			return true;
		}
		//else go down
		if(direction!="left" && findPath(maze, x, y+1, N,"right")){ //go right
			return true;
		}
		if(direction!="down" && findPath(maze, x-1, y, N, "up")){ //go up
			return true;
		}
		if(direction!="right" &&  findPath(maze, x, y-1, N, "left")){ //go left
			return true;
		}
		//if none of the options work out BACKTRACK undo the move
		solution[x][y] = 0;
		return false;
	}
	return false;
}

// this function will check if mouse can move to this cell
public boolean isSafeToGo(int[][] maze, int x, int y, int N) {
	// check if x and y are in limits and cell is not blocked
	if (x >= 0 && y >= 0 && x < N  && y < N && maze[x][y] != 0) {
		return true;
	}
	return false;
}
public void print(int [][] solution, int N){
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			System.out.print(" " + solution[i][j]);
		}
		System.out.println();
	}
}
public static void main(String[] args) {
	int N = 5;
	int[][] maze = { { 1, 0, 1, 1,1 }, { 1, 1, 1, 0,1 }, { 0, 0,0, 1, 1 },
			{ 0, 0, 0, 1,0 },{ 0, 0,0, 1, 1 } };
	RatInMaze r = new RatInMaze(N);
	r.solveMaze(maze, N);
}
    }

N-Queens

    public class NQueens {
static int[] result; // this array will store the result

// result[i]=j; means queen at i-th row is placed at j-th column.
// Queens placed at (x1, y1) and (x2,y2)
// x1==x2 means same rows, y1==y2 means same columns, |x2-x1|==|y2-y1| means
// they are placed in diagonals.
public boolean canPlace(int x2, int y2) {
	// This function will check if queen can be placed (x2,y2), or we can
	// say that Can queen at x2 row is placed at y2 column.
	// for finding the column for x2 row, we will check all the columns for
	// all the rows till x2-1.
	for (int i = 0; i < x2; i++) {
		//result[i] == y2 => columns are same
		//|i - x2| == |result[i] - y2| => in diagonals.
		if ((result[i] == y2)
				|| (Math.abs(i - x2) == Math.abs(result[i] - y2))) {
			return false;
		}
	}
	return true;
}
public void placeQueens(int x, int size) {
	for (int i = 0; i < size; i++) {
		//check if queen at xth row can be placed at i-th column.
		if (canPlace(x, i)) {
			result[x] = i; // place the queen at this position.
			if (x == size - 1) {
				System.out.println("Order of " + size + " queens"
						+ Arrays.toString(result));
			}
			placeQueens(x + 1, size);
		}
	}
}
public static void main(String[] args) {
	int n = 6;
	result = new int[n];
	NQueens i = new NQueens();
	i.placeQueens(0, n);
}
    }

SUDUKO SOLVER

Find empty cell, find int row, col number If there are no empty cells, return true, problem solved. For number from 1 to 9 a) If there if is safe for digit at cell[row][col] fill the cell[row][col]=number and recursively try fill in rest of grid b) If recursion successful, return true c) Else, undo the selection, cell[row][col]=0 and try another If all numbers are tried and solution not found, return false

    public class SUDOKU {
public static int[][] grid;

public boolean solveSUDOKU() {
	int row;
	int col;
	int[] blankCell = findBlankLocation();
	row = blankCell[0];
	col = blankCell[1];
	if (row == -1) {
		// means will have filled the grid, return;
		return true;
	}
	// we need to fill grid[row][col] cell
	for (int i = 1; i <= 9; i++) {
		// check if number i is safe for grid[row][col] cell
		if (isSafe(row, col, i)) {
			// means its safe to fill the number
			grid[row][col] = i;
			// fill the rest of the grid
			if (solveSUDOKU()) {
				return true;
			}
			// if we are here that means current selection of number didnt
			// work, revert back the changes
			grid[row][col] = 0;
		}
	}
	return false; // This will cause the backtracking
}

public boolean isSafe(int row, int col, int n) {
	// we need to check row contains number n OR
	// Column contains number n OR
	// Block in which cell appears contains number n
	// If Any of the above statement is true, return false
	if (!UsedInRow(row, n) && !UsedInColumn(col, n)
			&& !UsedInBox(row - row % 3, col - col % 3, n)) {
		return true;
	}
	return false;
}

// check if n not in particular row
public boolean UsedInRow(int row, int n) {
	for (int i = 0; i < 9; i++) {
		if (grid[row][i] == n) {
			return true;
		}
	}
	return false;
}

// check if n not in particular column
public boolean UsedInColumn(int col, int n) {
	for (int i = 0; i < 9; i++) {
		if (grid[i][col] == n) {
			return true;
		}
	}
	return false;
}

// check if n not in particular box
public boolean UsedInBox(int boxStartRow, int boxStartCol, int n) {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (grid[i + boxStartRow][j + boxStartCol] == n) {
				return true;
			}
		}
	}
	return false;
}

public int[] findBlankLocation() {
	int[] cell = new int[2]; // cell[0]-row cell[1] -column
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (grid[i][j] == 0) {
				cell[0] = i;
				cell[1] = j;
				return cell;
			}
		}
	}
	cell[0] = -1;
	cell[1] = -1;
	return cell; // means grid is full
}

public void print() {
	for (int row = 0; row < 9; row++) {
		if (row % 3 == 0) {
			System.out.println(); // for more readability
		}
		for (int col = 0; col < 9; col++) {
			if (col % 3 == 0) {
				System.out.print(" "); // for more readability
			}
			System.out.print(grid[row][col] + " ");

		}
		System.out.println();
	}
}

public static void main(String[] args) {
	grid = new int[][] { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
			{ 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
			{ 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
			{ 7, 0, 0, 0, 2, 0, 0, 0, 6 }, { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
			{ 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };
	SUDOKU s = new SUDOKU();
	if (s.solveSUDOKU()) {
		s.print();
	} else {
		System.out.println("NO SOLUTION");
	}
}
    }

Search word in a matrix

Cre­ate a solu­tion matrix of the same struc­ture as Matrix. Try each cell a start­ing point. Check cur­rent cell is not already used and char­ac­ter in it matches with the char­ac­ter in the word at index (starts will 0). Check if index = length of the word, means we have found the word. return true and print the solu­tion matrix. If above cri­te­ria matches, mark that cell with a num­ber When­ever any cell matches with the cri­te­ria, put a num­ber cor­re­spond­ing to it in solu­tion matrix. (start with 0 and keep incre­ment­ing it, it will show us the path for the word). Now try to solve rest of the prob­lem recur­sively by mak­ing index +1. Check all 8 direc­tions ( up, down, left right, diag­o­nally up-left, diag­o­nally up-right, diag­o­nally down-left, diag­o­nally down-right). Check the bound­ary con­di­tions as well If none of the 8 recur­sive calls return true, BACKTRACK and undo the changes ( put 0 to cor­re­spond­ing cell in solu­tion matrix) and return false. Choose dif­fer­ent start­ing point. If all the start­ing points tried and solu­tion not found, return false See the code for bet­ter understanding.

    public class WordMatrix {
public int[][] solution;
int path = 1;

// initialize the solution matrix in constructor.
public WordMatrix(int N) {
	solution = new int[N][N];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			solution[i][j] = 0;
		}
	}
}

public boolean searchWord(char[][] matrix, String word) {
	int N = matrix.length;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (search(matrix, word, i, j, 0, N)) {
				return true;
			}
		}
	}
	return false;
}

public boolean search(char[][] matrix, String word, int row, int col,
		int index, int N) {

	// check if current cell not already used or character in it is not not

	if (solution[row][col] != 0 || word.charAt(index) != matrix[row][col]) {
		return false;
	}

	if (index == word.length() - 1) {
		// word is found, return true
		solution[row][col] = path++;
		return true;
	}

	// mark the current cell as 1
	solution[row][col] = path++;		
	// check if cell is already used

	if (row + 1 < N && search(matrix, word, row + 1, col, index + 1, N)) { // go
																			// down
		return true;
	}
	if (row - 1 >= 0 && search(matrix, word, row - 1, col, index + 1, N)) { // go
																			// up
		return true;
	}
	if (col + 1 < N && search(matrix, word, row, col + 1, index + 1, N)) { // go
																			// right
		return true;
	}
	if (col - 1 >= 0 && search(matrix, word, row, col - 1, index + 1, N)) { // go
																			    // left
		return true;
	}
	if (row - 1 >= 0 && col + 1 < N
			&& search(matrix, word, row - 1, col + 1, index + 1, N)) {
		// go diagonally up right
		return true;
	}
	if (row - 1 >= 0 && col - 1 >= 0
			&& search(matrix, word, row - 1, col - 1, index + 1, N)) {
		// go diagonally up left
		return true;
	}
	if (row + 1 < N && col - 1 >= 0
			&& search(matrix, word, row + 1, col - 1, index + 1, N)) {
		// go diagonally down left
		return true;
	}
	if (row + 1 < N && col + 1 < N
			&& search(matrix, word, row + 1, col + 1, index + 1, N)) {
		// go diagonally down right
		return true;
	}

	// if none of the option works out, BACKTRACK and return false
	solution[row][col] = 0;
	path--;
	return false;
}

public void print() {
	for (int i = 0; i < solution.length; i++) {
		for (int j = 0; j < solution.length; j++) {
			System.out.print(" " + solution[i][j]);
		}
		System.out.println();
	}
}

public static void main(String[] args) {
	char[][] matrix = { { 't', 'z', 'x', 'c', 'd' },
			{ 'a', 'h', 'n', 'z', 'x' }, { 'h', 'w', 'o', 'i', 'o' },
			{ 'o', 'r', 'n', 'r', 'n' }, { 'a', 'b', 'r', 'i', 'n' } };
	WordMatrix w = new WordMatrix(matrix.length);
	if (w.searchWord(matrix, "horizon")) {
		w.print();
	} else {
		System.out.println("NO PATH FOUND");
	}

}
    }

Knight's Tour

    public class KnightTour {

int[][] solution;
int path = 0;

public KnightTour(int N) {
	solution = new int[N][N];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			solution[i][j] = 0;
		}
	}
}

public void solve() {
	if (findPath(0, 0, 0, solution.length)) {
		print();
	} else {
		System.out.println("NO PATH FOUND");
	}
}

public boolean findPath(int row, int column, int index, int N) {
	// check if current is not used already
	if (solution[row][column] != 0) {
		return false;
	}
	// mark the current cell is as used
	solution[row][column] = path++;
	// if (index == 50) {
	if (index == N * N - 1) {
		// if we are here means we have solved the problem
		return true;
	}
	// try to solve the rest of the problem recursively

	// go down and right
	if (canMove(row + 2, column + 1, N)
			&& findPath(row + 2, column + 1, index + 1, N)) {
		return true;
	}
	// go right and down
	if (canMove(row + 1, column + 2, N)
			&& findPath(row + 1, column + 2, index + 1, N)) {
		return true;
	}
	// go right and up
	if (canMove(row - 1, column + 2, N)
			&& findPath(row - 1, column + 2, index + 1, N)) {
		return true;
	}
	// go up and right
	if (canMove(row - 2, column + 1, N)
			&& findPath(row - 2, column + 1, index + 1, N)) {
		return true;
	}
	// go up and left
	if (canMove(row - 2, column - 1, N)
			&& findPath(row - 2, column - 1, index + 1, N)) {
		return true;
	}
	// go left and up
	if (canMove(row - 1, column - 2, N)
			&& findPath(row - 1, column - 2, index + 1, N)) {
		return true;
	}
	// go left and down
	if (canMove(row + 1, column - 2, N)
			&& findPath(row + 1, column - 2, index + 1, N)) {
		return true;
	}
	// go down and left
	if (canMove(row + 2, column - 1, N)
			&& findPath(row + 2, column - 1, index + 1, N)) {
		return true;
	}
	// if we are here means nothing has worked , backtrack
	solution[row][column] = 0;
	path--;
	return false;

}

public boolean canMove(int row, int col, int N) {
	if (row >= 0 && col >= 0 && row < N && col < N) {
		return true;
	}
	return false;
}

public void print() {
	DecimalFormat twodigits = new DecimalFormat("00");
	for (int i = 0; i < solution.length; i++) {
		for (int j = 0; j < solution.length; j++) {
			System.out.print("   " + twodigits.format(solution[i][j]));
		}
		System.out.println();
	}
}

public static void main(String[] args) {
	int N = 8;
	KnightTour i = new KnightTour(N);
	i.solve();
}
    }