Generate all binary strings

JavaView on GFG

Intuition

Backtracking: generate all 2^n binary strings recursively.

Algorithm

1DFS with current string. At each step: append 0 or 1, recurse to length n, backtrack.

Common Pitfalls

•Total 2^n strings. Use StringBuilder for efficiency.

Generate all binary strings.java

Java

// Approach: Backtracking. At each position place '0' or '1', recurse; collect complete strings.
// Time: O(2^n * n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<String> binstr(int n) {
        ArrayList<String> res = new ArrayList<>();
        if (n <= 0)
            return res;

        char[] cur = new char[n];
        generate(0, n, cur, res);
        return res;

    }

    private void generate(int idx, int n, char[] cur, ArrayList<String> res) {
        if (idx == n) {
            res.add(new String(cur));
            return;
        }

        cur[idx] = '0';
        generate(idx + 1, n, cur, res);

        cur[idx] = '1';
        generate(idx + 1, n, cur, res);
    }
}

Was this solution helpful?