This is trying to explain @StefanPochmann 's post in here:

https://discuss.leetcode.com/topic/106368/rewrite-of-contest-winner-s-solution

- The big idea is to use unsigned number from
`0`

to`2^n-1`

as bitmap to represent every`subset`

of`target`

; - then populate all of these subset from
`0`

to`2^n-1`

by trying to apply 1 sticker at each time. - Eventually you might or might not get the ultimate result
`2^n-1`

, which is`target`

, populated. - If not, it is -1;

```
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int n = target.size(), m = 1 << n; // if target has n chars, there will be m=2^n subset of characters in target
vector<uint> dp(m, -1); // use index 0 - 2^n as bitmaps to represent each subset of all chars of target
dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
for (int i = 0; i < m; i++) { // for every subset i, start from 00000...(emptyset) to 111111...(the target)
if (dp[i] == -1) continue;
for (string& s : stickers) { // try use each sticker as an char provider to populate a super-set of i,
int sup = i;
for (char c : s) { // to do that, for each char in the sticker,
for (int r = 0; r < n; r++) {
if (target[r] == c && !((sup >> r) & 1)) { // try apply it on a missing char in the subset of target
sup |= 1 << r;
break;
}
}
}
// after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
// would take, so you can try to update the superset's minsticker number with dp[sub]+1;
dp[sup] = min(dp[sup], dp[i] + 1);
}
}
return dp[m - 1]; // and the ultimate result
}
};
```

**Java**

```
class Solution {
public int minStickers(String[] stickers, String target) {
int n = target.length(), m = 1 << n; // if target has n chars, there will be m=2^n subset of characters in target
int[] dp = new int[m];
for (int i = 0; i < m; i++) dp[i] = Integer.MAX_VALUE; // use index 0 - 2^n as bitmaps to represent each subset of all chars in target
dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
for (int i = 0; i < m; i++) { // for every subset i, start from 000...000
if (dp[i] == Integer.MAX_VALUE) continue;
for (String s : stickers) { // try use each sticker as an char provider to populate 1 of its superset, to do that:
int sup = i;
for (char c : s.toCharArray()) { // for each char in the sticker, try apply it on a missing char in the subset of target
for (int r = 0; r < n; r++) {
if (target.charAt(r) == c && ((sup >> r) & 1) == 0) {
sup |= 1 << r;
break;
}
}
}
// after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
// would take, so you can try to update the superset's minsticker number with dp[sub]+1;
dp[sup] = Math.min(dp[sup], dp[i] + 1);
}
}
return dp[m - 1] != Integer.MAX_VALUE ? dp[m - 1] : -1;
}
}
```

Does these explanation make any sense?