# Backtracking

• 12-15-2010, 04:45 PM
pali185
Backtracking
Hello, I got the task to create a program with backtracking, i can not create. Could you write a theory as I do, or write a better program. Entering the example below:

On paper it is written long number 123456789. Insert between some digits signs + or -.
So that you incurred after evaluating the expression given number 100.
For example: 123-45-67 +89 = 100
Write a program that finds and displays all the solutions. Use backtracking.

THANK YOU.
• 12-15-2010, 04:49 PM
m00nchile
This is a problem that can be solved elegantly with recursion (of which backtracking is an integral part). Until we see an effort from you, I'm afraid you won't get much help, as this is not a "do my homework" forum.
• 12-17-2010, 02:08 PM
pali185
Examples are designed program that addresses the solution. But has several errors. This program should generate 3 ^ 9 = 19683 expressions (when calculating accurately). Instead, it generates a 9841 expressions. It is not a multiple of 3, but its half. The program input of Operators to 0 place - before '1' Strange input of the zero position and generates duplicate values. Can you help? Thank you.

//field in which I to insert operators
static String[] cislice = {"","1","","2","","3","","4","","5","","6","","7", "","8","","9"};
//field with operators
static String [] operatory = {"","+","-"};
...
private static void BacktrackingSto(int krok,int operator){
if(krok>cislice.length-1) return;

//print out genera generated expressions
for(int i=0;i<cislice.length;i++){
System.out.print(cislice[i]);
}System.out.println(); System.out.println();
j++; //number of generated expressions
System.out.println("Backtracking "+krok+", "+operator);

for(int i=0;i<3;i++){
cislice[krok]= operatory[operator];
BacktrackingSto(krok+2,i);
}
}