There are 2-dimentional array A[n][m] where n = 2*m.

Each array A[i] contains m unique integers in [0;n). Note, that elements in A[i] and A[j] can intersect if i != j. Each array A[i] is sorted.

Task: construct array B[n] that contains unique elements by taking only one element from each array of A. Or there is not solution if B[n] can't construct.

Example:

A[0] = {0, 2}
A[1] = {1, 2}
A[2] = {0, 3}
A[3] = {0, 3}

Result: 
Take A[0][1], A[1][0], A[2][0], A[3][1] => B = {2, 1, 0, 3}

I have a recursive algorithm that solves the task:

// level = 0 at first call
fn recursive_choice(a: &mut Vec<Vec<usize>>, b: &mut Vec<usize>, level: usize) {
    if level >= a.len() {
        return;
    }

    for idx in 0..a[level].len() {
        if !b.contains(&a[level][idx]) {
            b.push(a[level][idx]);
            recursive_choice(a, b, level   1);

            if a.len() == b.len() {
                return;
            } else {
                b.pop();
            }
        }
    }
}

Is there a better algorithm - and what is it? What is the complexity of this algorithm in the worst case?

CodePudding user response：

This can be viewed as the problem of finding a maximum matching between arrays and values. If the matching includes all arrays, then you have your answer. If it does not, then the answer is no.

Which can be solved by standard approaches such as the Blossom Algorithm in time O(n^4). If you're willing to use a more complex and optimized algorithm, you can reduce that to O(n^3).