Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Generate all binary strings

MEDIUMProblemSolveExternal Links

Description

Given a positive integer n, generate all possible binary strings of length n.

A binary string is a string that contains only the characters '0' and '1'. Since each of the n positions can independently be either '0' or '1', there are exactly 2^n such strings in total.

Return all the binary strings in ascending (lexicographic) order.

Examples

Example 1

Input: n = 2

Output: ["00", "01", "10", "11"]

Explanation: With 2 positions and 2 choices per position, we get 2² = 4 binary strings. In ascending order: "00" (both bits zero), "01" (second bit set), "10" (first bit set), "11" (both bits set).

Example 2

Input: n = 3

Output: ["000", "001", "010", "011", "100", "101", "110", "111"]

Explanation: With 3 positions, we get 2³ = 8 binary strings. Each string represents a unique combination of three binary digits, listed from smallest to largest when interpreted as binary numbers.

Example 3

Input: n = 1

Output: ["0", "1"]

Explanation: With only 1 position, there are exactly two binary strings: "0" and "1".

Constraints

  • 1 ≤ n ≤ 20

Editorial

Brute Force - Iterative Enumeration

Intuition

The simplest way to think about generating all binary strings of length n is to realize that each binary string of length n is just the binary representation of some number between 0 and 2^n − 1.

For example, if n = 3, the numbers 0 through 7 in binary are:

  • 0 → "000"
  • 1 → "001"
  • 2 → "010"
  • 3 → "011"
  • 4 → "100"
  • 5 → "101"
  • 6 → "110"
  • 7 → "111"

So the approach is straightforward: loop through every integer from 0 to 2^n − 1, convert each integer into its n-bit binary string, and collect all the results. Since the integers are naturally in ascending order, the binary strings will also come out in ascending (lexicographic) order.

Step-by-Step Explanation

Let's trace through with n = 2:

Step 1: Compute total = 2^n = 2² = 4. We will iterate i from 0 to 3.

Step 2: i = 0. Convert 0 to 2-bit binary:

  • Check bit at position 1 (from left): (0 >> 1) & 1 = 0 → '0'
  • Check bit at position 0: (0 >> 0) & 1 = 0 → '0'
  • Binary string = "00". Add to result.
  • Result so far: ["00"]

Step 3: i = 1. Convert 1 to 2-bit binary:

  • Bit at position 1: (1 >> 1) & 1 = 0 → '0'
  • Bit at position 0: (1 >> 0) & 1 = 1 → '1'
  • Binary string = "01". Add to result.
  • Result so far: ["00", "01"]

Step 4: i = 2. Convert 2 to 2-bit binary:

  • Bit at position 1: (2 >> 1) & 1 = 1 → '1'
  • Bit at position 0: (2 >> 0) & 1 = 0 → '0'
  • Binary string = "10". Add to result.
  • Result so far: ["00", "01", "10"]

Step 5: i = 3. Convert 3 to 2-bit binary:

  • Bit at position 1: (3 >> 1) & 1 = 1 → '1'
  • Bit at position 0: (3 >> 0) & 1 = 1 → '1'
  • Binary string = "11". Add to result.
  • Result so far: ["00", "01", "10", "11"]

Step 6: i = 4 which equals total (4), so we stop. Final result: ["00", "01", "10", "11"].

Iterative Enumeration — Converting Numbers to Binary Strings — Watch how each integer from 0 to 2^n − 1 is converted to its n-bit binary representation and appended to the result list.

Algorithm

  1. Compute total = 2^n (the number of binary strings to generate)
  2. For each integer i from 0 to total − 1:
    a. Build an n-character string by extracting bits of i from the most significant to the least significant
    b. For each bit position j from n−1 down to 0, append '1' if the j-th bit of i is set, else '0'
    c. Add the resulting string to the result list
  3. Return the result list

Code

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> generateBinaryStrings(int n) {
        vector<string> result;
        int total = 1 << n; // 2^n
        
        for (int i = 0; i < total; i++) {
            string s;
            for (int j = n - 1; j >= 0; j--) {
                s += ((i >> j) & 1) ? '1' : '0';
            }
            result.push_back(s);
        }
        
        return result;
    }
};
class Solution:
    def generateBinaryStrings(self, n: int) -> list[str]:
        result = []
        total = 1 << n  # 2^n
        
        for i in range(total):
            s = ""
            for j in range(n - 1, -1, -1):
                s += '1' if (i >> j) & 1 else '0'
            result.append(s)
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateBinaryStrings(int n) {
        List<String> result = new ArrayList<>();
        int total = 1 << n; // 2^n
        
        for (int i = 0; i < total; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = n - 1; j >= 0; j--) {
                sb.append(((i >> j) & 1) == 1 ? '1' : '0');
            }
            result.add(sb.toString());
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

We iterate through all 2^n numbers. For each number, we extract n bits to build the binary string. Total work: 2^n iterations × n bit extractions per iteration = O(n × 2^n).

Space Complexity: O(n)

Excluding the output storage, we use O(n) space for building each individual binary string. The output itself requires O(n × 2^n) space to store all strings, but that is inherent to the problem's output requirement.

Why This Approach Is Not Efficient

The iterative enumeration approach achieves the same O(n × 2^n) time complexity as any correct solution — after all, we must produce 2^n strings of length n, so this lower bound is unavoidable. However, the approach has several practical and educational limitations:

1. Bit manipulation overhead: For each of the 2^n numbers, we perform n bit-shift and bitwise-AND operations to extract individual bits. While each operation is O(1), this per-string overhead adds up — especially compared to recursive construction where each character is placed directly.

2. Poor generalizability: This approach relies on the one-to-one correspondence between integers and binary strings. If the problem adds constraints (e.g., "no consecutive 1s", "at most k ones"), this method requires generating all 2^n strings first and then filtering — potentially wasting significant work. A recursive approach can prune invalid branches early.

3. Integer overflow risk for large n: While n ≤ 20 fits comfortably in a 32-bit integer (2^20 ≈ 10^6), conceptually this approach ties string generation to integer size limits. The recursive approach has no such coupling.

Key insight for improvement: Instead of mapping numbers to strings after the fact, we can build strings character-by-character using recursion. At each position, we make a binary choice: place '0' or place '1'. This directly constructs strings without any intermediate number representation, and naturally generalizes to constrained variants through backtracking.

Optimal Approach - Recursion with Backtracking

Intuition

Think of building a binary string as filling in a form with n blank boxes. For each box, you have exactly two stamps: a '0' stamp and a '1' stamp. You start at the leftmost box and work your way right.

At the first box, you stamp '0'. Then you move to the next box and stamp '0' again. You keep going until all boxes are filled — that gives you one complete string. Then you backtrack: erase the last stamp, try '1' instead, and continue forward again.

This is the essence of recursion with backtracking:

  • Recurse forward: At each position, try placing '0', then recurse to fill the remaining positions.
  • Backtrack: Once you've explored all possibilities with '0' at this position, replace it with '1' and recurse again.
  • Base case: When all n positions are filled, you've formed a complete binary string — add it to the result.

By always trying '0' before '1' at each position, the strings are naturally generated in ascending lexicographic order. The recursion tree has depth n and branches into 2 paths at each level, producing all 2^n leaves (complete strings).

Step-by-Step Explanation

Let's trace through with n = 2. We start with an empty string and fill positions 0 and 1.

Step 1: Call generate("", position=0). The string is empty. We need to fill position 0.

Step 2: Place '0' at position 0 → string becomes "0". Recurse to position 1.

Step 3: Place '0' at position 1 → string becomes "00". Position equals n (2), so "00" is a complete string. Add "00" to result. Result: ["00"].

Step 4: Backtrack from position 1. Remove '0', try '1' at position 1 → string becomes "01". Position equals n, so "01" is complete. Add "01" to result. Result: ["00", "01"].

Step 5: Backtrack from position 1 back to position 0. We've tried both choices at position 1 with '0' at position 0. Now try '1' at position 0 → string becomes "1". Recurse to position 1.

Step 6: Place '0' at position 1 → string becomes "10". Complete string. Add "10" to result. Result: ["00", "01", "10"].

Step 7: Backtrack from position 1. Try '1' → string becomes "11". Complete string. Add "11" to result. Result: ["00", "01", "10", "11"].

Step 8: Backtrack to position 0. Both choices exhausted. Recursion complete. Final result: ["00", "01", "10", "11"].

Recursion with Backtracking — Building Binary Strings (n = 2) — Watch the recursion tree grow as we explore all binary choices at each position, backtracking after each complete string to try the alternative.

Algorithm

  1. Create an empty result list and a mutable string of length n initialized to all '0's
  2. Define a recursive function generate(string, position):
    a. Base case: If position equals n, the string is complete — add a copy to the result list and return
    b. Recursive step — try '0': Set string[position] = '0', then call generate(string, position + 1)
    c. Recursive step — try '1': Set string[position] = '1', then call generate(string, position + 1)
    d. (Optional backtrack): Reset string[position] = '0' to restore state
  3. Call generate(string, 0) to start from position 0
  4. Return the result list

Code

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    void generate(string& s, int pos, vector<string>& result) {
        if (pos == s.size()) {
            result.push_back(s);
            return;
        }
        
        // Try placing '0' at current position
        s[pos] = '0';
        generate(s, pos + 1, result);
        
        // Try placing '1' at current position
        s[pos] = '1';
        generate(s, pos + 1, result);
    }
    
    vector<string> generateBinaryStrings(int n) {
        vector<string> result;
        string s(n, '0');
        generate(s, 0, result);
        return result;
    }
};
class Solution:
    def generateBinaryStrings(self, n: int) -> list[str]:
        result = []
        
        def generate(s: list[str], pos: int):
            if pos == n:
                result.append("".join(s))
                return
            
            # Try placing '0' at current position
            s[pos] = '0'
            generate(s, pos + 1)
            
            # Try placing '1' at current position
            s[pos] = '1'
            generate(s, pos + 1)
        
        generate(['0'] * n, 0)
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    private void generate(char[] s, int pos, List<String> result) {
        if (pos == s.length) {
            result.add(new String(s));
            return;
        }
        
        // Try placing '0' at current position
        s[pos] = '0';
        generate(s, pos + 1, result);
        
        // Try placing '1' at current position
        s[pos] = '1';
        generate(s, pos + 1, result);
    }
    
    public List<String> generateBinaryStrings(int n) {
        List<String> result = new ArrayList<>();
        char[] s = new char[n];
        generate(s, 0, result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

The recursion tree has 2^n leaf nodes, each representing a complete binary string of length n. At each leaf, we copy the n-character string into the result list, costing O(n). The internal nodes contribute O(1) work each (setting a character and making recursive calls). Total internal nodes: 2^n − 1. So total time is O(n × 2^n) for copying strings at leaves plus O(2^n) for internal processing, giving O(n × 2^n) overall.

Space Complexity: O(n)

The recursion stack goes n levels deep (one level per position). We reuse a single mutable string of length n. Excluding the output storage, auxiliary space is O(n). The output itself requires O(n × 2^n) space, but that is inherent to the problem.