<p>We are given <code>n</code> different types of <code>stickers</code>. Each sticker has a lowercase English word on it.</p>

<p>You would like to spell out the given string <code>target</code> by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.</p>

<p>Return <em>the minimum number of stickers that you need to spell out </em><code>target</code>. If the task is impossible, return <code>-1</code>.</p>

<p><strong>Note:</strong> In all test cases, all words were chosen randomly from the <code>1000</code> most common US English words, and <code>target</code> was chosen as a concatenation of two random words.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stickers = [&quot;with&quot;,&quot;example&quot;,&quot;science&quot;], target = &quot;thehat&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong>
We can use 2 &quot;with&quot; stickers, and 1 &quot;example&quot; sticker.
After cutting and rearrange the letters of those stickers, we can form the target &quot;thehat&quot;.
Also, this is the minimum number of stickers necessary to form the target string.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stickers = [&quot;notice&quot;,&quot;possible&quot;], target = &quot;basicbasic&quot;
<strong>Output:</strong> -1
Explanation:
We cannot form the target &quot;basicbasic&quot; from cutting letters from the given stickers.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == stickers.length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>1 &lt;= stickers[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= target.length &lt;= 15</code></li>
	<li><code>stickers[i]</code> and <code>target</code> consist of lowercase English letters.</li>
</ul>

class Solution {
    int res;
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = stickers.size();

        vector<int> org_want(26, 0);

        for(char c : target){
           org_want[c-'a']++;
        }

        vector<int> idx(26, 0);

        int tmp_idx = 0;
        for(int i=0;i<26;i++){
            if(org_want[i] > 0) idx[i] = tmp_idx++;
            else idx[i] = -1;
        }

        vector<int> want;

        for(int num : org_want){
            if(num > 0) want.push_back(num);
        }

        vector<vector<int>> dp;
        for(int i=0;i<n;i++){
            bool valid_sticker = false;
            vector<int> tmp(tmp_idx, 0);
            for(char c : stickers[i]){
                int j = idx[c-'a'];
                if(j >= 0) {
                    tmp[j]++;
                    valid_sticker = true;
                }
            }
            if(valid_sticker) dp.push_back(tmp);
        }

        int start = 0;
        for(int i=0;i<dp.size();i++){
            for(int j=start;j<dp.size();j++){
                if(i != j){
                    bool dominate = true;
                    for(int k=0;k<tmp_idx;k++){
                        if(dp[i][k] > dp[j][k]) {
                            dominate = false;
                            break;
                        }
                    }
                    if(dominate) {
                        vector<int> tmp_d = dp[i];
                        dp[i] = dp[start];
                        dp[start++] = tmp_d;
                        break;
                    }
                }
            }
        }



        res = INT_MAX;

        helper(dp, want, target.size(), 0, start, 0);

        return (res == INT_MAX) ? -1 : res;
    }

    void helper(vector<vector<int>>& dp, vector<int> want, int n, int cur_len, int ID, int total){
        if(cur_len >= n){
            res = min(res, total);
            return;
        }
        if(total >= res) return;
        if(ID == dp.size()) return;

        helper(dp, want, n, cur_len, ID + 1, total);

        bool valid = false;

        for(int i=0;i<want.size();i++){
            if(want[i] > 0 && dp[ID][i] > 0){
                valid = true;
                cur_len += min(dp[ID][i], want[i]);
                want[i] -= dp[ID][i];
            }
        }

        // useful sticker
        if(valid == true){
            helper(dp, want, n, cur_len, ID, total + 1);
        }


    }
};
74478