> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/unsensored/find-sequences.md).

# Find sequences

There are two 1, two 2, ... two n in a sequence of numbers. Find if there exists any permutations such that the number of of elements between two identical number `n` equals to `n`.

For example: `n` is 4, then `41312432` satisfies the requirement.

## Solutions

1. **dfs**

```cpp
vector<int> solve(int n) {
    vector<int> used(n + 1), res(2 * n, -1);

    function<bool(int)> find = [&](int i) {
        if (i == 2 * n) return true;
        if (res[i] != -1) return find(i + 1);

        for (int num = 1; num <= n; num++) {
            int next = i + num + 1;
            if (used[num]
                || next >= 2 * n
                || res[next] != -1) continue;
            used[num] = true;
            res[i] = res[next] = num;
            if (find(i + 1))
                return true;
            res[i] = res[next] = -1;
            used[num] = false;
        }
        return false;
    };
    find(0);
    return res;
}

int main() {
    int n; cin >> n;
    cout << solve(n) << endl;
}
```