Pattern · Quay luiTrung bình
Tất Cả Tập ConSubsets
Hiểu bài
Cho mảng các số nguyên phân biệt nums. Trả về tất cả tập con (power set) có thể — bao gồm tập rỗng và tập chính nó.
Ví dụ:
ts
nums = [1, 2, 3]
output = [
[], [1], [2], [3],
[1,2], [1,3], [2,3],
[1,2,3]
]
// 2³ = 8 tập con (n phần tử → 2ⁿ tập con)
nums = [0]
output = [[], [0]]Với mỗi phần tử có 2 lựa chọn: chọn hoặc không chọn.
Quay lui (backtracking) liệt kê đủ 2ⁿ nhánh.
Cách cơ bản
O(n × 2ⁿ) time — 2ⁿ tập con, mỗi cái tốn O(n) để buildts
// Bit masking — dùng số nhị phân đại diện cho tập con
function subsetsBitmask(nums: number[]): number[][] {
const n = nums.length
const result: number[][] = []
for (let mask = 0; mask < (1 << n); mask++) {
const subset: number[] = []
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) subset.push(nums[i])
}
result.push(subset)
}
return result
}Vì sao cách này chậm:
Bit masking là cách thức khác để sinh 2ⁿ tập con.
- Backtracking tự nhiên hơn và dễ mở rộng cho các biến thể (subset with duplicates, subset sum).
- Cả hai có cùng Big-O.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.