Check if concatenation of any permutation of given list of arrays generates the given array | C ++ program for the above approach ; Function to check if it is possible to obtain array by concatenating the arrays in list pieces [ ] ; Stores the index of element in the given array arr [ ] ; Traverse over the list pieces ; If item size is 1 and exists in map ; If item contains > 1 element then check order of element ; If end of the array ; Check the order of elements ; If order is same as the array elements ; Increment idx ; If order breaks ; Otherwise ; Return false if the first element doesn 't exist in m ; Return true ; Driver Code ; Given target list ; Given array of list ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( vector < int > & arr , vector < vector < int > > & pieces ) { unordered_map < int , int > m ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) m [ arr [ i ] ] = i + 1 ; for ( int i = 0 ; i < pieces . size ( ) ; i ++ ) { if ( pieces [ i ] . size ( ) == 1 && m [ pieces [ i ] [ 0 ] ] != 0 ) { continue ; } else if ( pieces [ i ] . size ( ) > 1 && m [ pieces [ i ] [ 0 ] ] != 0 ) { int idx = m [ pieces [ i ] [ 0 ] ] - 1 ; idx ++ ; if ( idx >= arr . size ( ) ) return false ; for ( int j = 1 ; j < pieces [ i ] . size ( ) ; j ++ ) { if ( arr [ idx ] == pieces [ i ] [ j ] ) { idx ++ ; if ( idx >= arr . size ( ) && j < pieces [ i ] . size ( ) - 1 ) return false ; } else { return false ; } } } else { return false ; } } return true ; } int main ( ) { vector < int > arr = { 1 , 2 , 4 , 3 } ; vector < vector < int > > pieces { { 1 } , { 4 , 3 } , { 2 } } ; if ( check ( arr , pieces ) ) { cout << " Yes " ; } else { cout << " No " ; } return 0 ; }