1
class Solution {
2
 public:
3
  int dp[50][1 << 15];
4
  int solve(int ind, int mask, vector<string> &stickers, string &target) {
5
    if (mask == 0) return 0;
6
    if (ind == stickers.size()) return 1e8;
7
    if (dp[ind][mask] != -1) return dp[ind][mask];
8
    vector<int> mp(26, 0);
9
    bool flag = false;
10
    int ans = 1e8;
11
    for (int i = 0; i < stickers[ind].size(); i++) mp[stickers[ind][i] - 'a']++;
12
    for (int i = 0; i < target.size(); i++) {
13
      if (mp[target[i] - 'a'] > 0 && (mask & (1 << i))) {
14
        flag = true;
15
        break;
16
      }
17
    }
18
    if (flag) // Check if we can use any of the characters in sticker[ind]
19
    {
20
      int tempMask = mask;
21
      for (int i = 0; i < target.size(); i++) {
22
        if (mp[target[i] - 'a'] > 0 && (tempMask & (1 << i))) {
23
          tempMask = tempMask ^ (1 << i);
24
          mp[target[i] - 'a']--;
25
        }
26
      }
27
      ans = min(ans, 1 + solve(ind, tempMask, stickers,
28
                               target)); // Take those characters, and make call
29
                                         // on same index
30
    }
31
    ans = min(ans, solve(ind + 1, mask, stickers,
32
                         target)); // Skip sticker[ind] and proceed
33
    return dp[ind][mask] = ans;
34
  }
35

36
  int minStickers(vector<string> &stickers, string target) {
37
    int n = target.size();
38
    memset(dp, -1, sizeof(dp));
39
    int ans = solve(0, (1 << n) - 1, stickers, target);
40
    if (ans == 1e8) return -1;
41
    return ans;
42
  }
43
};