Subsets

+10

Bạn nhận được một danh sách nums gồm các số nguyên khác nhau. Hãy trả về mọi tập con của danh sách, bao gồm tập rỗng và toàn bộ danh sách, nên n giá trị tạo thành 2^n tập con. Viết các giá trị trong mỗi tập con theo thứ tự tăng dần, rồi liệt kê các tập con theo thứ tự từ điển: so sánh từng giá trị của hai tập con, vị trí khác nhau đầu tiên sẽ quyết định thứ tự; nếu một tập con là phần đầu của tập con kia thì tập con đó đứng trước. Với [1, 2], đáp án là [[], [1], [1, 2], [2]].

Hàm

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: các giá trị đều khác nhau, theo thứ tự bất kỳ
Trả vềinteger-2d-array: mọi tập con, mỗi tập được sắp xếp theo thứ tự tăng dần và được liệt kê theo thứ tự từ điển

Ràng buộc

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Tất cả giá trị trong nums đều khác nhau.
nums có thể ở bất kỳ thứ tự nào.

Ví dụ

Đầu vào: nums = [3, 1, 2]
Đầu ra: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Giải thích: Ba giá trị tạo ra 2^3 = 8 tập con. [1, 2] đứng trước [1, 2, 3] vì nó là phần đầu, và [1, 2, 3] đứng trước [1, 3] vì 2 nhỏ hơn 3 ở vị trí thứ hai.

Đầu vào: nums = [0]
Đầu ra: [[], [0]]
Giải thích: Một giá trị có hai tập con: bỏ qua giá trị đó để được [], hoặc lấy giá trị đó để được [0]. Tập con rỗng luôn đứng trước.

Đầu vào: nums = [5, -2]
Đầu ra: [[], [-2], [-2, 5], [5]]
Giải thích: Các giá trị được sắp xếp theo thứ tự là -2 và 5, nên [-2, 5] được viết theo thứ tự đó. Mọi tập con (subset) chứa -2 đều đứng trước [5], vì -2 nhỏ hơn 5.

Câu hỏi mở rộng

Bạn có thể tạo cùng danh sách mà không dùng đệ quy, bằng cách xây dựng từng tập hợp con trực tiếp từ tập hợp đứng trước nó không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Có 2^n tập con, vì vậy không phương pháp nào thực hiện ít hơn O(2^n) thao tác. Câu hỏi thực sự là làm thế nào để tạo mỗi tập con đúng một lần, theo đúng thứ tự yêu cầu, mà không phải sắp xếp 1024 danh sách sau đó. Quay lui trên các giá trị đã sắp xếp, ghi lại mỗi nút của cây quyết định khi đi vào nút đó, sẽ duyệt các tập con theo đúng thứ tự từ điển.

Mặt nạ bit, rồi sắp xếp

Ý tưởng

Xếp các giá trị đã sắp xếp vào các vị trí từ 0 đến n-1. n bit của một số cho biết vị trí tương ứng có được chọn hay không, nên các số từ 0 đến 2^n-1 biểu diễn mọi tập con, mỗi tập đúng một lần: với [1, 2, 3], mặt nạ 5 có dạng nhị phân 101 và biểu diễn [1, 3]. Đọc các bit từ vị trí 0 trở lên sẽ viết mỗi tập con theo thứ tự tăng dần.

Các mặt nạ xuất hiện sai thứ tự: mặt nạ 2 là [2] còn mặt nạ 3 là [1, 2], nên [2] đứng trước [1, 2]. Sắp xếp bằng cách so sánh lần lượt từng giá trị và xếp tiền tố lên trước sẽ khắc phục điều này. Cách sắp xếp đó cần khoảng n × 2^n phép so sánh, mỗi phép so sánh tối đa n giá trị, tương đương khoảng 10^5 lần đọc khi n = 10, lượng công việc mà thuật toán quay lui không bao giờ thực hiện.

Thuật toán

Sắp xếp nums để mọi tập con đều có thứ tự tăng dần.
Với mỗi mask từ 0 đến 2^n-1, lấy các giá trị ở những vị trí có bit được bật.
Sắp xếp danh sách các tập con: tại vị trí đầu tiên mà hai tập con khác nhau, tập con có giá trị nhỏ hơn sẽ đứng trước; nếu một tập con hết phần tử trước thì tập con đó đứng trước.
Trả về danh sách đã sắp xếp.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Quay lui: chọn, khám phá, bỏ chọn

Ý tưởng

Hãy hình dung các tập con như một cái cây. Gốc là tập con rỗng, và bên dưới một nút, bạn có thể thêm bất kỳ giá trị nào lớn hơn giá trị cuối cùng của nó: với [1, 2, 3], [1] có các nút con là [1, 2] và [1, 3]. Mỗi tập con xuất hiện đúng một lần, vì chỉ có một cách viết tăng dần, và mọi nút đều là một đáp án, kể cả các nút bên trong.

Quay lui (backtracking) đi qua cây bằng một danh sách dùng chung, path, và ghi lại một bản sao của danh sách khi đến mỗi nút. Nhờ vậy, mỗi nút cha đứng trước các nút con, và việc thử các nút con từ giá trị nhỏ nhất trở lên sẽ hoàn tất một nhánh trước khi chuyển sang nhánh tiếp theo: thứ tự từ điển mà không cần sắp xếp.

Cây có 2^n nút và mỗi bản sao tốn tối đa n: O(n × 2^n), bằng kích thước của đáp án, cộng thêm O(n) cho đường đi và ngăn xếp lời gọi.

Thuật toán

Sắp xếp các giá trị.
Viết explore(start). Trước tiên, hàm này thêm một bản sao của path vào kết quả.
Sau đó, với mỗi chỉ số i từ start đến cuối, thêm values[i] vào path (chọn), gọi explore(i+1) (khám phá) rồi xóa giá trị cuối cùng (bỏ chọn).
Gọi explore(0) với một đường đi rỗng rồi trả về kết quả.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Lỗi thường gặp và trường hợp biên

Thêm chính path thay vì một bản sao. Khi đó, mọi phần tử đều trỏ đến cùng một danh sách, vốn trống khi quá trình duyệt kết thúc, nên bạn trả về 2^n bản sao của [].
Quên sắp xếp nums. Với [3, 1, 2], cây tạo ra [3, 1], không theo thứ tự tăng dần.
Chỉ ghi nhận ở các nút lá, như khi tạo hoán vị. Mỗi nút là một tập con, nên bạn trả về quá ít kết quả.
Gọi đệ quy với start+1 thay vì i+1. Khi đó, một giá trị có thể đứng sau một giá trị lớn hơn hoặc chính nó, tạo ra các danh sách như [3, 2] và [1, 3, 3].
Ghi nhận các nút lá của cây gồm hoặc loại trừ. Cách này tìm ra tất cả 2^n tập con, nhưng nếu chọn gồm trước thì danh sách đầy đủ đứng đầu, còn nếu chọn loại trừ trước thì [3] đứng trước [2].

Câu hỏi thường gặp3

Có bao nhiêu tập hợp con của một tập hợp có n phần tử?

2^n. Mỗi phần tử được chọn hoặc không được chọn, độc lập với các phần tử khác, nên số lựa chọn được nhân lên. Ba giá trị tạo thành 8 tập con và mười giá trị tạo thành 1024 tập con, tính cả tập con rỗng và tập hợp đầy đủ.

Độ phức tạp thời gian của bài toán tập hợp con là gì?

O(n × 2^n). Có 2^n tập con và việc ghi ra một tập con cần tối đa n bước, vì vậy chỉ riêng việc trả về kết quả đã tốn chừng đó. Quay lui đạt giới hạn này với O(n) bộ nhớ bổ sung; dùng mặt nạ bit rồi sắp xếp sẽ làm tăng thêm một hệ số n.

Bạn xử lý các giá trị trùng lặp trong Subsets như thế nào?

Sắp xếp các giá trị, rồi trong vòng lặp của hàm hỗ trợ, bỏ qua giá trị bằng với giá trị đứng ngay trước nó ở cùng cấp: i > start và values[i] == values[i-1]. Bản sao đầu tiên đã khám phá mọi tập con có sử dụng nó, vì vậy nhánh bắt đầu từ bản sao thứ hai sẽ tạo lại những tập con tương tự.

def subsets(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 1, 2]

Đầu ra mong đợi

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]