Sunday, 30 August 2015

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;
        }
    }
}