Problem

Generate All Strings of n bits, consider A[0..n-1] is an array of size n.

Examples

Example 1

n = 3
Output:
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]

Solution

Method 1 - Recursion

Recursion is key here.

  • create a integer array of size n.
  • Now if we think of every bit, it can take 2 values, 0 and 1.
  • starting from the end of the string, set the bit 0 and 1 and make recursive calls

Code

Java
public class Solution {

	public List<String> generateBitStrings(int n) {
		List<String> ans = new ArrayList<>();
		int[] bits = new int[n];
		dfs(n, bits, 0, ans);
		return ans;
	}

	private void dfs(int n, int[] bits, int curr, List<String> ans) {
		if (curr == n) {
			ans.add(convertToString(bits));
			return;
		}

		// Set the current bit to 0
		bits[curr] = 0;
		dfs(n, bits, curr + 1, ans);

		// Set the current bit to 1 and recurse
		bits[curr] = 1;
		dfs(n, bits, curr + 1, ans);
	}

	private String convertToString(int[] bits) {
		StringBuilder sb = new StringBuilder();

		for (int bit: bits) {
			sb.append(bit);
		}

		return sb.toString();
	}
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n) assuming stack space