Binary Strings Without Two 1s in a Row

/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : The strings.
 * Approach: Backtracking with a rule.
 * Time    : O(F(n) * n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Build the string character by character. A 1 is allowed only if the previous character is not 1.
        static void build(String current, int length, java.util.List<String> result) {
            // Step 2: Base case. The string is complete: save it.
            if (current.length() == length) {
                result.add(current);
                return;
            }

            // Step 3: A 0 is always allowed. We try 0 first, so the result is in ascending order.
            build(current + "0", length, result);

            // Step 4: A 1 is allowed only if the string does not end with 1.
            if (current.isEmpty() || current.charAt(current.length() - 1) != '1') {
                build(current + "1", length, result);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long n) {
        java.util.List<String> result = new java.util.ArrayList<>();
        build("", (int) n, result);
        return result.toArray(new String[0]);
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(String.join("\n", solve(n)));
    }
}