# Backtracking - Find Unique Binary String

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, Backtracking

## Problem

Given an array of strings `nums`

containing `n`

**unique** binary strings each of length `n`

, return *a binary string of length* `n`

*that does not appear in*

`nums`

*. If there are multiple answers, you may return*.

**any**of them**Example 1:**

1
2
3

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

**Example 2:**

1
2
3

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

**Example 3:**

1
2
3

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

## Solution

This is bit different, but definitely not a complicated problem. We need to basically find all the binary numbers of length `n`

and if we find any of that does not belong to the input array then return the one does not belong.

Here we shall try to first solve to find all the combinations up to length `n`

. Please refer my other problems if you are unable to understand the below solution. We are using template 2 here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def find_binary(n):
output =[]
def dfs(k,path):
if k==n:
output.append(''.join(path))
return
for c in ['0','1']:
path.append(c)
dfs(k+1,path)
path.pop()
dfs(0,[])
return output

1
2
3
4

print(find_binary(2))
['00', '01', '10', '11']
print(find_binary(3))
['000', '001', '010', '011', '100', '101', '110', '111']

Now the only thing we have do is to modify the above and return a missing binary number. Let’s first create a `map`

using the input `nums`

.

1

binary_map = {s for s in nums}

Inside the `dfs()`

we need to validate if the `path`

is present in the `binary_map`

, if not then return it, otherwise return `None`

1
2
3

if k==n:
found = ''.join(path)
return None if found in binary_map else found

Finally, inside the `for`

loop if we get a response which is not `None`

we return that.

1
2
3
4
5
6

for c in ['0','1']:
path.append(c)
found= dfs(k+1,path)
if found is not None:
return found
path.pop()

At the end, return the `dfs()`

function.

1

return dfs(0,[])

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def find_binary(nums):
n = len(nums)
binary_map = {s for s in nums}
def dfs(k, path):
if k == n:
found = ''.join(path)
return None if found in binary_map else found
for c in ['0', '1']:
path.append(c)
found = dfs(k+1, path)
if found is not None:
return found
path.pop()
return dfs(0, [])