<p>Given an array of strings <code>nums</code> containing <code>n</code> <strong>unique</strong> binary strings each of length <code>n</code>, return <em>a binary string of length </em><code>n</code><em> that <strong>does not appear</strong> in </em><code>nums</code><em>. If there are multiple answers, you may return <strong>any</strong> of them</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;01&quot;,&quot;10&quot;]
<strong>Output:</strong> &quot;11&quot;
<strong>Explanation:</strong> &quot;11&quot; does not appear in nums. &quot;00&quot; would also be correct.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;00&quot;,&quot;01&quot;]
<strong>Output:</strong> &quot;11&quot;
<strong>Explanation:</strong> &quot;11&quot; does not appear in nums. &quot;10&quot; would also be correct.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;111&quot;,&quot;011&quot;,&quot;001&quot;]
<strong>Output:</strong> &quot;101&quot;
<strong>Explanation:</strong> &quot;101&quot; does not appear in nums. &quot;000&quot;, &quot;010&quot;, &quot;100&quot;, and &quot;110&quot; would also be correct.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 16</code></li>
	<li><code>nums[i].length == n</code></li>
	<li><code>nums[i] </code>is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li>All the strings of <code>nums</code> are <strong>unique</strong>.</li>
</ul>

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

class Solution {
public:
    void solve(vector<int>& v, int index, vector<vector<int>>& ans, vector<string>& nums) {
        if (index == nums[0].size()) {
            ans.push_back(v);
            return;
        }
        v[index] = 1;
        solve(v, index + 1, ans, nums); // Recursive call with the bit set to 1
        v[index] = 0;
        solve(v, index + 1, ans, nums); // Recursive call with the bit set to 0
    }

    string findDifferentBinaryString(vector<string>& nums) {
        vector<vector<int>> ans;
        vector<int> v(nums[0].size(), 0); // Initialize a vector of 0s with the same size as the binary strings
        solve(v, 0, ans, nums);

        for (auto& binary : ans) {
            string binaryString;
            for (int bit : binary) {
                binaryString += to_string(bit);
            }
            if (find(nums.begin(), nums.end(), binaryString) == nums.end()) {
                return binaryString;
            }
        }
        return ""; 
    }
};
266996