<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>

bool operator<=(const vector<int>& a, const vector<int>& b) {
    // check if a is dominated by b
    for (int i = 0; i < a.size(); i++)
        if (a[i] > b[i]) return false;
    return true;
};

bool operator>=(const vector<int>& a, const vector<int>& b) {
    // check if a dominates b
    for (int i = 0; i < a.size(); i++)
        if (a[i] < b[i]) return false;
    return true;
};

ostream& operator<<(ostream& out, const vector<int>& a) {
    for (int x : a) out << x << ", ";
    return out;
}

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        // return minStickers_DFS(stickers, target);
        return minStickers_DP(stickers, target);
    }

    int minStickers_DP(vector<string>& stickers, string target) {
        // dp[state] := minimum number of stickers needed to cover letters in state
        // dp[state] = min_s{ dp[state'] | state'+s => state and dp[state'] != -1, s is a sticker }
        int N = target.size();
        // Index stickers and target
        vector<int> count(26, 0), index(26, -1);
        vector<int> task;
        for (char c : target) count[c - 'a']++;
        for (int i = 0; i < count.size(); i++) {
            if (count[i] == 0) continue;
            index[i] = task.size();
            task.push_back(count[i]);
        }
        vector<vector<int>> stickerCounts;
        for (const string& sticker : stickers) {
            vector<int> st(task.size(), 0);
            bool b = false;
            for (char c : sticker) {
                if (index[c - 'a'] == -1) continue;
                st[index[c - 'a']]++;
                b = true;
            }
            if (b) stickerCounts.push_back(st);
        }
        // update states
        vector<int> dp(1 << N, -1); dp[0] = 0;
        for (int state = 0; state < (1 << N); state++) {
            if(dp[state] == -1) continue;
            for (const vector<int>& st : stickerCounts) {
                vector<int> stCount = st;
                int now = state;
                for (int i = 0; i < N; i++) {
                    if ((state >> i) & 1) continue;
                    if (stCount[index[target[i] - 'a']]-- > 0)
                        now |= (1 << i);
                }
                if (dp[now] == -1) dp[now] = dp[state] + 1;
                dp[now] = min(dp[now], dp[state] + 1);
            }
        }
        return dp[(1 << N) - 1];
    }

    int minStickers_DFS(vector<string>& stickers, string target) {
        // T, number of all chars in target
        // TC: O( C(N+T-1, N-1) * T ), equal to number of ways to distribute chars to stickers, times T, 
        /// since each in each recursion, it takes O(T) to update task states.
        // SC: O(N * T), candidates and task
        int n = stickers.size();
        // Index task.
        vector<int> task;  // compressed counts for target
        vector<int> count(26, 0), index(26, -1);  // map count to task
        for (char c : target) count[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                index[i] = task.size();
                task.push_back(count[i]);
            }
        }
        auto getCandidate = [&index, &task](const string& s) -> vector<int> {
            vector<int> cand(task.size(), 0);
            for (char c : s) {
                if (index[c - 'a'] != -1)
                    cand[index[c - 'a']]++;
            }
            return move(cand);
        };
        // Index candidate stickers, and filter candidates.
        vector<vector<int>> candidates;
        for (const string& s : stickers) {
            vector<int> v = getCandidate(s);
            if (isEmpty(v)) continue;
            int bFilter = false;
            for (int i = 0; i < candidates.size();) {  // NOTE: no i++, and size() will updated here
                if (candidates[i] >= v) {
                    bFilter = true;
                    break;
                }
                if (candidates[i] <= v) {
                    candidates.erase(candidates.begin() + i);
                } else {
                    i++;
                }
            }
            if (!bFilter) candidates.push_back(v);
        }
        int ans = target.length() + 1;  // Init smaller answer to prune earlier, better than INT_MAX.
        solve(candidates, 0, task, 0, ans);
        return ans <= target.length() ? ans : -1;
    }

    void solve(const vector<vector<int>>& candidates, int index, vector<int>& task, int cnt, int& ans) {
        if (isEmpty(task)) {
            ans = min(ans, cnt);
            return;
        }
        if (cnt >= ans) return;  // pruning: candidate's answer won't be better
        for (int i = index; i < candidates.size(); i++) {
            if (inCommon(candidates[i], task)) {  // pruning: useless candidate for current task
                for (int j = 0; j < task.size(); j++)
                    task[j] -= candidates[i][j];
                solve(candidates, i, task, cnt + 1, ans);
                for (int j = 0; j < task.size(); j++)
                    task[j] += candidates[i][j];
            }
        }
    } 

    bool inCommon(const vector<int>& a, const vector<int>& b) {
        // check if a cross b is not null
        for (int i = 0; i < a.size(); i++)
            if (a[i] > 0 && b[i] > 0) return true;
        return false;
    };

    bool isEmpty(const vector<int>& a) {
        return accumulate(a.begin(), a.end(), 0, [](int accu, int x) -> int {
            return accu + (x > 0);
        }) == 0;
    }
};
129503