CODEWITHSUNDEEP
algorithmbacktracking
Suthari Sandeep
Suthari Sandeep

Reputation: 31

Backtracking for generating binary Strings of ‘n’ bits. Can some one please explain how backtracking is done here?

For generating binary strings of n bits, I have the following recursive solution.

public static void main(String[] args) {
    int n = 4;
    int[] array = new int[n];
    generateBinaryStrings(array, n);
}

public static void generateBinaryStrings(int[] array, int N) {
    if (N < 1) {
        System.out.println(Arrays.toString(array));
    } else {
        array[N - 1] = 0;
        generateBinaryStrings(array, N - 1);
        array[N - 1] = 1;
        generateBinaryStrings(array, N - 1);
    }
}

The solution works fine, but I'm told that backtracking is used here as said in many articles on this problem.Can someone please explain me how backtracking is done here?

Upvotes: 0

Views: 893

Answers (3)

Mohd Akbar
Mohd Akbar

Reputation: 111

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. Full in depth study of backtracking can be done here. https://en.wikipedia.org/wiki/Backtracking But as far as your question is concerned the backtracking used here is the first line of the definition. Backtracking is a general algorithm for finding all solutions to some computational problem. So here as you are finding the all possible solutions of binary digits of length 'n' so it becomes a backtracking solution and the algorithm bactracks to find other solutions when it knows that the length 'n' is finished. Backtracking works in a tree like manner as shown in figure below. Whenever it reaches the end it backtracks to fetch the other output and we get the output in this order as recursion uses a stack. bactracking tree

And this is the output your code is getting

[0, 0, 0, 0]

[1, 0, 0, 0]

[0, 1, 0, 0]

[1, 1, 0, 0]

[0, 0, 1, 0]

[1, 0, 1, 0]

[0, 1, 1, 0]

[1, 1, 1, 0]

[0, 0, 0, 1]

[1, 0, 0, 1]

[0, 1, 0, 1]

[1, 1, 0, 1]

[0, 0, 1, 1]

[1, 0, 1, 1]

[0, 1, 1, 1]

[1, 1, 1, 1]

Upvotes: 0

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36431

This is not backtracking, this is just pure recursion. Backtracking is (usually) a recursive algorithm where you cut and get back a track as soon as you know that is it not useful to follow it.

Upvotes: 1

CS Pei
CS Pei

Reputation: 11047

A backtracking recursively goes through all different ways how a solution can be constructed.

The line array[N-1] = 0; will set the current last element to 0. Then the next line generateBinaryStrings(array, N - 1); will generate all the possible solutions for a string with N - 1 elements (the substring that is before array[N-1]). This will be the half solution of all N elements because this is for array[N-1] = 0.

The other half should be for a string with array[N-1] = 1 and that is what the next two lines of code doing.

Upvotes: 0

Related Questions