## 1640. Check Array Formation Through Concatenation

You are given an array of distinct integers `arr` and an array of integer arrays `pieces`, where the integers in `pieces` are distinct. Your goal is to form `arr` by concatenating the arrays in `pieces` in any order. However, you are not allowed to reorder the integers in each array `pieces[i]`.

Return `true` if it is possible to form the array `arr` from `pieces`. Otherwise, return `false`.

Example 1:

```Input: arr = , pieces = []
Output: true
```

Example 2:

```Input: arr = [15,88], pieces = [,]
Output: true
Explanation: Concatenate `` then ``
```

Example 3:

```Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces.
```

Example 4:

```Input: arr = [91,4,64,78], pieces = [,[4,64],]
Output: true
Explanation: Concatenate `` then `[4,64]` then `````

Example 5:

```Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false
```

Constraints:

• `1 <= pieces.length <= arr.length <= 100`
• `sum(pieces[i].length) == arr.length`
• `1 <= pieces[i].length <= arr.length`
• `1 <= arr[i], pieces[i][j] <= 100`
• The integers in `arr` are distinct.
• The integers in `pieces` are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

## Rust Solution

``````struct Solution;

impl Solution {
fn can_form_array(arr: Vec<i32>, pieces: Vec<Vec<i32>>) -> bool {
let n = arr.len();
Self::dp(n, &arr, &pieces)
}

fn dp(n: usize, arr: &[i32], pieces: &[Vec<i32>]) -> bool {
if n == 0 {
return true;
}
for piece in pieces {
let m = piece.len();
if m <= n && arr[n - m..n] == piece[0..m] && Self::dp(n - m, arr, pieces) {
return true;
}
}
false
}
}

#[test]
fn test() {
let arr = vec!;
let pieces = vec_vec_i32![];
let res = true;
assert_eq!(Solution::can_form_array(arr, pieces), res);
let arr = vec![15, 88];
let pieces = vec_vec_i32![, ];
let res = true;
assert_eq!(Solution::can_form_array(arr, pieces), res);
let arr = vec![49, 18, 16];
let pieces = vec_vec_i32![[16, 18, 49]];
let res = false;
assert_eq!(Solution::can_form_array(arr, pieces), res);
let arr = vec![91, 4, 64, 78];
let pieces = vec_vec_i32![, [4, 64], ];
let res = true;
assert_eq!(Solution::can_form_array(arr, pieces), res);
let arr = vec![1, 3, 5, 7];
let pieces = vec_vec_i32![[2, 4, 6, 8]];
let res = false;
assert_eq!(Solution::can_form_array(arr, pieces), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.