Pyth, 17 15 11 bytes

AQ}Ym-dH./G 

AQ}Ym-dH./G AQ Save the input into G, H. ./G Get all partitions of G. m-dH Check if the parts are in H. }Y The empty list should be present if and only if the string can be made. 

Old version

AQ&G}GsMs.pMy*HlG 

Pyth, 17 15 11 14 bytes

AQ|!G}Ym-dH./G 

The requirement for the empty string changed, adding 3 bytes.

Explanation

AQ|!G}Ym-dH./G AQ Save the input into G, H. ./G Get all partitions of G. m-dH Check if the parts are in H. }Y The empty list should be present if and only if the string can be made... |!G ... or the string might be empty. 

Old versions

AQ}Ym-dH./G 

AQ}Ym-dH./G AQ Save the input into G, H. ./G Get all partitions of G. m-dH Check if the parts are in H. }Y The empty list should be present if and only if the string can be made.   AQ&G}GsMs.pMy*HlG 

Pyth, 17 15 bytes

AQ}Ym-cGdHyStlG 

Shorter and runs in the lifespan of the universe!

Explanation

AQ}Ym-cGdHyStlG AQ Save the input into G, H.   yStlG  Get all subsets of [1, ..., len(G) - 1].  m cGd  Chop G at the positions defined by each subset.   -  H Check if the pieces are in H. }Y The empty list should be present if and only if the string can be made. 

Old version

AQ&G}GsMs.pMy*HlG 

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

AQ&G}GsMs.pMy*HlG AQ Save the input into G, H. *HlG Repeat the list of substrings for each character of G. y Take the power set. .pM Take every permutation of each set of substrings. sMs Get a list of all the joined strings. }G Check if G is one of them. &G Make sure G is not empty. 

Pyth, 17 15 11 bytes

AQ}Ym-dH./G 

Shorter and runs in the lifespan of the universe!

Explanation

AQ}Ym-dH./G AQ Save the input into G, H. ./G Get all partitions of G. m-dH Check if the parts are in H. }Y The empty list should be present if and only if the string can be made. 

Old version

AQ&G}GsMs.pMy*HlG 

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

AQ&G}GsMs.pMy*HlG AQ Save the input into G, H. *HlG Repeat the list of substrings for each character of G. y Take the power set. .pM Take every permutation of each set of substrings. sMs Get a list of all the joined strings. }G Check if G is one of them. &G Make sure G is not empty. 

Pyth, 17 bytes

AQ&G}GsMs.pMy*HlG 

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

AQ&G}GsMs.pMy*HlG AQ Save the input into G, H. *HlG Repeat the list of substrings for each character of G. y Take the power set. .pM Take every permutation of each set of substrings. sMs Get a list of all the joined strings. }G Check if G is one of them. &G Make sure G is not empty. 

Pyth, 17 15 bytes

AQ}Ym-cGdHyStlG 

Shorter and runs in the lifespan of the universe!

Explanation

AQ}Ym-cGdHyStlG AQ Save the input into G, H. yStlG Get all subsets of [1, ..., len(G) - 1]. m cGd Chop G at the positions defined by each subset. - H Check if the pieces are in H. }Y The empty list should be present if and only if the string can be made. 

Old version

AQ&G}GsMs.pMy*HlG 

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

AQ&G}GsMs.pMy*HlG AQ Save the input into G, H. *HlG Repeat the list of substrings for each character of G. y Take the power set. .pM Take every permutation of each set of substrings. sMs Get a list of all the joined strings. }G Check if G is one of them. &G Make sure G is not empty.