Question

Given a positive integer `n`, return an array of all the binary strings of length n that *DO NOT* contain consecutive `1`s.

```
Input: n (Integer)
Output: [Str] (Array of Strings)
```

# Example

```
Input: 2
Output: ["00", "01", "10"]

Input: 3
Output: ["000", "001", "010", "100", "101"]
```

# Constraints

```
Time Complexity: O(2^N)
Auxiliary Space Complexity: O(2^N)
```

Solution

public static ArrayList<String> result;
	public static ArrayList<String> nonConsecutiveOnes(int n){
		result = new ArrayList<String>();
		nonConsecutiveOnesHelper("", n);
		return result;
	}
	
	private static void nonConsecutiveOnesHelper(String s, int n) {
		
		//base case
		if(s.length() == n) {
			result.add(s);
			return;
		}
		
		//string with '0' ending
		nonConsecutiveOnesHelper(s+"0",n);
		
		if(!s.endsWith("1"))
			nonConsecutiveOnesHelper(s+"1",n);
	}