A footpath has n lamps in a row. To save power the council never lights two adjacent lamps. A
pattern is written as a string of "1" (lit) and "0" (dark). Return every allowed pattern of length
n, in any order.
Examples
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Input: n = 1
Output: ["0", "1"]
Input: n = 0
Output: [""]
Explanation: the empty footpath has exactly one (empty) pattern.
Constraints
0 <= n <= 14
Goals
- Branch on two choices per position and skip the branch that breaks a rule
- Check a constraint against the previous choice only