# [1255. Maximum Score Words Formed by Letters](https://leetcode.com/problems/maximum-score-words-formed-by-letters/description/)

# 1. Tóm tắt đề bài

Cho một danh sách các từ $words$, và danh sách các ký tự $letters$, và $score$ tương ứng với điểm số của từng ký tự.

Ta cần chọn ra một tập con $w$ trong danh sách $words$ thỏa mãn:

- Có thể sử dụng các ký tự trong danh sách $letters$ để tạo ra tất cả các từ trong $w$, mỗi ký tự trong $letters$ được sử dụng một lần.
- Tổng số điểm của các ký tự được sử dụng là cao nhất có thể. (Nếu sử dụng ký tự thứ $i$ trên bảng chữ cái, sẽ được cộng $score_i$ điểm).

##### Giới hạn

$1 \le |words| \le 14$
$1 \le |words[i]| \le 15$
$1 \le |letters| \le 100$
$0 \le score_i \le 10$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(2 ^ {|words|} * \Sigma(words_i))$**

Bài toán này chính là bài toán chọn tập hợp con tối ưu, từ tập hợp cha chính là $words$.

Ta nhận thấy: $|words| \le 14$, vì vậy, ta có thể duyệt toàn bộ tập con của nó ($2^{14}$ tập hợp). Với mỗi tập hợp con, ta có thể tính xem có đủ chữ trong $letters$ cho nó không, và tính tổng số điểm của các ký tự được sử dụng.

# 3. Lời giải chi tiết

Từ ý tưởng, ta có thể xử lý bài toán này giống như bài chọn subset bình thường.

Các bạn lưu ý ở đoạn code của mình sẽ sử dụng mảng $remain$ để lưu số lượng các ký tự còn lại trong $letters$, cũng như sẽ sử dụng một biến $ok$ để kiểm tra xem trong mảng $remain$ còn đủ chữ để chọn từ hiện tại không.

Code mẫu: https://leetcode.com/problems/maximum-score-words-formed-by-letters/submissions/1266421049/

### Độ phức tạp thuật toán

Thời gian: $O(2 ^ {|words|} * \Sigma(words_i))$

Bộ nhớ mở rộng: $O(n)$

# 4. Kết luận & Gợi ý mở rộng

Các bạn có thể xem các bài cơ bản hơn để duyệt subset:

[78. Subsets](https://leetcode.com/problems/subsets/description/)
[90. Subsets II](https://leetcode.com/problems/subsets-ii/description/)
[2151. Maximum Good People Based on Statements](https://leetcode.com/problems/maximum-good-people-based-on-statements/description/)