Subset Sum problem | Java and Backtracking

Hello Friends,

Today I am here with you with another problem based upon recursion and back tracking.

Suppose we have an array of positive integer elements: 'arr' and a positive number: 'targetSum'.
We need to all the possible subsets of the array elements such that adding the elements of any of the found subsets results in 'targetSum'.

Suppose we have arr= { 2, 3, 4, 5 } and targetSum = 7 then our subsets are {2,5},{3,4}.


Friends I have tried to solve this using Back-tracking, please find the code in java below.

package com.recursion.backtracking;

public class SubSetSum {
    public static void main(String[] args) {
        int[] input = { 2, 3, 4, 5 };
        int targetSum = 7;
        SubSetSum subSetSum = new SubSetSum();
        subSetSum.findSubSets(input, targetSum);
    }

    private int[] set;
    private int[] selectedElements;
    private int targetSum;
    private int numOfElements;

    public void findSubSets(int[] set, int targetSum) {
        this.set = set;
        this.numOfElements = set.length;
        this.targetSum = targetSum;
        selectedElements = new int[numOfElements];
        quicksort(set, 0, numOfElements-1);
        int sumOfAllElements = 0;
        for(int element : set){
            sumOfAllElements += element;
        }
        findSubSets(0, 0, sumOfAllElements);
    }

    private void findSubSets(int sumTillNow, int index, int sumOfRemaining) {
        selectedElements[index] = 1; // selecting element at index : 'index'
        if (targetSum == set[index] + sumTillNow) {
            print();
        }

        // (sum + set[index] + set[index+1] <= targetSum) : this condition
        // ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.
        if ((index + 1 < numOfElements) && (sumTillNow + set[index] + set[index + 1] <= targetSum)) {
            findSubSets(sumTillNow + set[index], index + 1, sumOfRemaining - set[index]);
        }

        // now exploring the other path: not Selecting the element at index:
        // 'index'
        selectedElements[index] = 0;

        // (sum + set[index+1] <= targetSum) : this condition ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.

        // (sum + sumOfRemaining - set[index] >= targetSum) ensures the total
        // sum of all the elements by excluding the current element may achieve
        // the target sum, if in case the resultant sum is less than the target
        // sum then exploring this path is of no use
        if ((index + 1 < numOfElements) && (sumTillNow + set[index + 1] <= targetSum)
                && (sumTillNow + sumOfRemaining - set[index] >= targetSum)) {
            findSubSets(sumTillNow, index + 1, sumOfRemaining - set[index]);
        }
    }

    private void print() {
        for (int i = 0; i < numOfElements; i++) {
            if (selectedElements[i] == 1) {
                System.out.print(set[i]+" ");
            }
        }
        System.out.println();
    }

    private void quicksort(int[] arr, int start, int end) {
        if (start < end) {
            swap(arr, (start + (end - start) / 2), end);
            int pIndex = partition(arr, start, end);
            quicksort(arr, start, pIndex - 1);
            quicksort(arr, pIndex + 1, end);
        }
    }

    private int partition(int[] arr, int start, int end) {
        int pIndex = start, pivot = arr[end];
        for (int i = start; i < end; i++) {
            if (arr[i] < pivot) {
                swap(arr,pIndex,i);
                pIndex++;
            }
        }
        swap(arr,pIndex,end);
        return pIndex;
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

Make correct equation to achieve a given RHS. | Java and Backtracking

Hello Friends,

I am with you with another problem based upon back tracking.

If we have an integer array A[] and another integer value K, we need to find is there a sequence of  '+', '-' exists  such that if applied on the elements of A produce K. The operations need to be applied without changing the relative position of the array elements.

Friends I have used recursion with back tracking to solve this problem, please find the code below for the same.

package com.recursion.backtracking;

import java.util.Arrays;

public class MakeValidEquation {
    public static void main(String[] args) {
        int numbers[] = { 2, 3, 4, 5 };
        int RHS = 6;
        
        MakeValidEquation equation = new MakeValidEquation(numbers, RHS);
        boolean isRHSAchievable = equation.makeValidEquation(0, numbers.length);
        if(isRHSAchievable){
            System.out.println("Operations : "+Arrays.toString(equation.operators));
        }else{
            System.out.println("RHS can not be achieved by +, - on the numbers");
        }
    }

    public MakeValidEquation(int[] numbers, int RHS) {
        this.numbers = numbers;
        int n = numbers.length;
        this.RHS = RHS;
        operators = new char[n-1];
    }

    private char[] operators;
    private int[] numbers;
    private int RHS;

    public boolean makeValidEquation(int i, int n) {
        if (i == n - 1) {
            int result = numbers[0];
            for (int j = 0; j <= n - 2; j++) {
                if (operators[j] == '+') {
                    result = result + numbers[j + 1];
                } else if (operators[j] == '-') {
                    result = result - numbers[j + 1];
                }
            }
            return result == RHS;
        }
        operators[i] = '+';
        if(makeValidEquation(i+1, n)){
            return true;
        }else {
            // try next option
            operators[i] = '-';
            if(makeValidEquation(i+1, n)){
                return true;
            }
            else return false;
        }
    }
}

Solution in java for : Finding if a path exists from start to end cell in a maze | Back Tracking and Dynamic Programming

Hello Friends,

Today I am here with you with a recursion problem. Today we have a little tough problem.

Suppose we have a maze and we need to determine if a path exits from starting point  to the last point in the maze. Maze is represented by a 2-d-matrix. Lets call this matrix 'maze'. maze[0][0] represents the starting point and maze[rows-1][columns-1] be the end point. Any cell 'maze[i][j]' can be used as a part of the path if it contains 1 and can be reached from immediate top, left, right or bottom cells. Cells containing 0 are the ones which can not be used in the path.

Friends I have tried solving this using two Approaches.
    1. Recursion [Back Tracking] : Depth search First approach : DFS
    2. Dynamic Programming.

**Note that Dynamic programming approach will fail for few examples where path exists by traversing upwards or left side like below example

1 1 1 1 0 0 0 0
0 0 0 1 0 1 1 1
0 1 1 1 0 1 0 1
0 1 0 0 0 1 0 1
0 1 1 1 1 1 0 1


Friends please find below the code for this problem.

package com.recursion.backtracking;

public class Maze {
    public static void main(String[] args) {
        int mazeForDFS[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        int mazeForDP[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        boolean isPathAvailableDFS = isPathAvailable(mazeForDFS, 0, 0, mazeForDFS.length, mazeForDFS[0].length);
        boolean isPathAvailableDP = isPathAvailable(mazeForDP);
        System.out.println("DFS way : " + isPathAvailableDFS);
        System.out.println("DP  way : " + isPathAvailableDP);
    }

    public static final int VISITED = 0;

    /**
     * This is a recursive approach based upon recursion and Back tracking. If a
     * end point is reached then true is returned all the way up to the first
     * calling of the method, else false is returned. False is propagated  down
     * the call stack if all the options [top, left, right, down] are explored
     * and no other cell is left to explore.
     * 
     * @param maze
     * @param i
     * @param j
     * @param rows
     * @param columns
     * @return true if path exists else returns false;
     */
    public static boolean isPathAvailable(int[][] maze, int i, int j, int rows, int columns) {
        if (i == rows - 1 && j == columns - 1) {
            return true;
        }
        maze[i][j] = VISITED;
        if (j + 1 < columns && maze[i][j + 1] != VISITED) {
            if (isPathAvailable(maze, i, j + 1, rows, columns)) {
                return true;
            }
        }
        if (i + 1 < rows && maze[i + 1][j] != VISITED) {
            if (isPathAvailable(maze, i + 1, j, rows, columns)) {
                return true;
            }
        }
        if (j - 1 >= 0 && maze[i][j - 1] != VISITED) {
            if (isPathAvailable(maze, i, j - 1, rows, columns)) {
                return true;
            }
        }
        if (i - 1 >= 0 && maze[i - 1][j] != VISITED) {
            if (isPathAvailable(maze, i - 1, j, rows, columns)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method uses Dynamic programming to solve the problem. It exploits
     * the information for all the first row and column information and then
     * verifies the rest of the cells if they are reachable. In case they are
     * not reachable this method marks them as 0, as they are as good as cells
     * with value = 0;
     * 
     */
    public static boolean isPathAvailable(int[][] maze) {
        int rows = maze.length;
        int coloumns = maze[0].length;
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < coloumns; j++) {
                if (maze[i][j] == 1 && maze[i - 1][j] == 0 && maze[i][j - 1] == 0) {
                    maze[i][j] = 0;
                }
            }
        }
        return maze[rows - 1][coloumns - 1] == 1;
    }
}

Compute 'x' raised to power 'n' in O(logN) time using Java

Hello friends,

In  continuation to the recursive algorithms, I am here with you with another problem.

Suppose we have a number 'x' a another positive Integer 'n'. We need to find the value of 'x' raised to power to 'n'.

Friends please find below the code in java for this.

package com.recursion.power;

import java.util.Scanner;

/**
*
* @author krishna.k
*
*         This class computes the value of 'x' raised to power of 'n' in time
*         complexity of O(log n). 'x' is Integer, and n is a positive Integer
*         including 0.
*
*
*
*
*/
public class PowerComputation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the value of x (base)");
        int x = sc.nextInt();
        System.out.println("Enter a positve integer n (power)");
        int n = sc.nextInt();
        System.out.println("Value of " + x + " raised to power " + n + " is " + computePower(x, n));
    }

    public static int computePower(int x, int n) {
        if (x == 0 || x == 1 || n == 1) {
            return x;
        }
        if (n == 0) {
            return 1;
        }
        int temp = computePower(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            return x * temp * temp;
        }
    }
}

Print the elements of the array in straight order and in reverse order using Recursion in Java

Hello friends,

I am here with another question in continuation to our simple recursive algorithm based questions.

If we have an array of numbers, we need to print the elements of the array in straight order and in reverse order. 

We can easily do this using iteration but for learning purpose lets try doing this using recursion.

Note that to print the elements in the reverse order I have used two methods, one uses simple index based manipulation but lets observe the other method : printReverseInterestingWay(). While other method prints the elements as it visits the element first time but this method prints the element during re-visit (following the recurrence method calls in stack)

Friends Please find the code below.

package com.recursion.printarray;

public class StraightReversePrintArray {
    public static void main(String[] args) {
        int[] input = { 1, 2, 3, 4, 6, 8 };
        int size = input.length;
        System.out.println("Straight printing of the Array: ");
        printStraight(input, size, 0);
        System.out.println("Reverse printing of the Array: ");
        printReverse(input, size, 0);
        System.out.println("Reverse printing of the Array using interesting way: ");
        printReverseInterestingWay(input, size, 0);
    }

    public static void printStraight(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[i]);
            printStraight(input, size, i+1);
        }
    }

    public static void printReverse(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[size-i-1]);
            printReverse(input, size, i+1);
        }
    }
    
    public static void printReverseInterestingWay(int[] input, int size, int i){
        if(i < size){
            printReverseInterestingWay(input, size, i+1);
            System.out.println(input[i]);
        }
    }
}

Sum of first N natural numbers by recursion in Java

Dear Friends,

I am here with you with another simple problem.

If we have a natural number, N then we need to find the sum of first N natural numbers.

This has a simple solution which can be simply printing the value of N*(N+1)/2. For learning purpose lets try this problem using recursion. Friends please find below the code using recursion.

package com.recursion.sum.numbers;

import java.util.Scanner;

/**
 * This can be solved using simple formula for sum of first n natural numbers
 * but for learning purpose we are solving it using Recursion
 * 
 * @author krishna.k
 *
 */
public class SumOfFirstNNumbers {
    public static void main(String[] args) {
        System.out.println("Enter the Number");
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println("Sum of first "+ number+" numbers is "+computeSum(number));
    }

    public static int computeSum(int number) {
        if(number == 1){
            return 1;
        }
        return number + computeSum(number-1);
    }
}

Sum of digits of a number N using recursion in Java

Hello friends,

I am here with you with an easy problem.

Given a number N , we need to output the sum of the digits of the number N.

This can be solved using iteration but for learning purpose lets do it using recursion.

Friends, please find the code below for this problem.

package com.recursion.sumofdigits;

import java.util.Scanner;

public class SumOfDigitsOfNumN {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the Number: ");
        int number = sc.nextInt();
        System.out.println("Sum of digits is "+getSum(number));
    }
    
    public static int getSum(int number){
        int lsd = number%10; // least significant digit
        int remainingNum = number/10;
        if(remainingNum == 0){
            return lsd;
        }
        return lsd+getSum(remainingNum);
    }
}