# Thread: need help with backtracking

1. ## need help with backtracking

Hi
i have beed studying algorithms for some time but in teoretics so i decided to implement a beacktracking algorithm to generate some permutations though i respected all the instruactions my cod is not working proper :confused:
here is the cod i wrote
Java Code:
```public class permutation_bktr {
public static void main(String args[]) {
System.out.println("give n");
java.util.Scanner in = new java.util.Scanner(System.in);
int n = in.nextInt();
in.close();
int sp=1;
int [] x = new int[n];
int k = 0;
x[1] = 0;

while (k>=0) {
x[k] = x[k] + 1 ;
if(x[k]>n) k-=1;
else {
for(int i=0;i<k-1;i++)
if(x[i]==x[k]) sp=0;
else sp=1;
if(sp==1)
if(k==n)
for(int i=0;i<k;i++ ) {
System.out.print(x[i]);
System.out.println();     }
else {
k+=1;
x[k] = 0;  //not sure why but i get the out of bound exception here
}
}
}

}
}```
if someones knows what;s wrong help plz

2. i have been thinking of this and i have found the mistake that give the out of bound exception
well the algorithm saies that k values is the first position of the array wich is 0 in java so in stand of x[1] = 0 it should be x[0] = 0 becous x[o] is the first element of the java array ....
the secound mistake is the while condition becous it sdould stop when there are no more values that can be added in the first array position and the result to be a valid solution so it should be while(k>0) becous when k==0 it's the end condition....

the coud is like this

Java Code:
```public class permutari_bktr {
public static void main(String args[]) {
System.out.println("give n");
java.util.Scanner in = new java.util.Scanner(System.in);
int n = in.nextInt();
in.close();
int sp=1;
int [] x = new int[n];
int k = 0;
x[0] = 0;

while (k>0) {      //here is the while
x[k] = x[k] + 1 ;
if(x[k]>n) k=k-1;
else {
for(int i=0;i<k-1;i++)
if(x[i]==x[k]) sp=0;
else sp=1;
if(sp==1) {
if(k==n) {
for(int i=0;i<k;i++ ) {
System.out.print(x[i]);
System.out.println();     } //end of the for
} // if (k==n)
else {
k+=1;
x[k] = 0;
} // else from if(k==n)
} //if(sp==1)
} // else from if(x[k]==n)
} //end of the while
} //end of main
} // end of class```
but now i get a new problem:
the cod compile and startes but after reading the array length it stopes with build successful with no output :confused:

someone have an ideea why there is no output
Last edited by Dumisan; 02-17-2010 at 01:12 PM.

3. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
Your comments say there's a while loop, but I can't see one.
Also, you really must indent properly...lack of decent indentation makes code-flow almost impossible to see.
Also also, use brackets even for single lined if statements, or controls. It makes sure you don't miss something simple.

4. i have marked the while
about the indent well it should work like that but is not :(
now i'm remacking the code based on the backtracking general implementation to see if somehow i missed something on the conditions

5. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
If you're using netbeans then Shift-Alt-F to format it.

6. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
That code will never go into the while:

Java Code:
```      [B]int k = 0;[/B]
x[0] = 0;

while ([B]k>0[/B]) {      //here is the while```

7. ok so here is the cod formated and with the while conditon modified

Java Code:
```public class permutari_bktr {
public static void main(String args[]) {
System.out.println("give n");
java.util.Scanner in = new java.util.Scanner(System.in);
int n = in.nextInt();
in.close();
int sp = 1;
int[] x = new int[n];
int k = 0;
x[0] = 0;
while (k >= 0) {
x[k] = x[k] + 1;
if (x[k] > n) {
k = k - 1;
} else {
for (int i = 0; i < k - 1; i++) {
if (x[i] == x[k]) {
sp = 0;
} else {
sp = 1;
}
}
if (sp == 1) {
if (k == n) {
for (int i = 0; i < k; i++) {
System.out.print(x[i]);
System.out.println();
} //end of the for
} // if (k==n)
else {
k += 1;
x[k] = 0;  //i got a ArrayIndexOutOfBoundsException here
} // else from if(k==n)
} //if(sp==1)
} // else from if(x[k]==n)
} //end of the while
} //end of main
} // end of class```
it's like my first post it's the same cod

8. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
The exception will tell you what index you're attempting to read.
You can then compare that number to the number you entered...and possibly spot why it's going wrong.

9. run:
give n
4
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
at learn.permutari_bktr.main(permutari_bktr.java:42)
Java Result: 1
BUILD SUCCESSFUL (total time: 6 seconds)

10. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
OK, so going through this bit:

Java Code:
```                    if (k == n) {
for (int i = 0; i < k; i++) {
System.out.print(x[i]);
System.out.println();
} //end of the for
} // if (k==n)
else {
k += 1;
x[k] = 0;  //i got a ArrayIndexOutOfBoundsException here
} // else from if(k==n)```
What happens when you get to this code with k = 3?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•