Tại sao quay lui? . Nếu chúng ta thiết kế thuật toán một cách thông minh, chúng ta có thể khiến logic quay lui hoạt động cho mình và tạo ra tất cả các tập hợp con có thể
Ý tưởng là nếu chúng ta có N số phần tử bên trong một mảng, thì chúng ta có chính xác hai lựa chọn cho mỗi phần tử đó, hoặc chúng ta đưa phần tử đó vào tập hợp con của mình hoặc chúng ta không bao gồm phần tử đó. Vì vậy, chiến lược lấy hoặc không lấy sẽ xây dựng một cây nhị phân giả gồm các lựa chọn chỉ trả lại các lá cho mỗi kết hợp dẫn đến bộ quyền lực
Cây đệ quy cho ví dụ trên sẽ như thế này
các bước giải quyết
Chúng tôi chỉ có thể xây dựng tập hợp con có kích thước khác nhau trong một mảng tôi. e. tập hợp con[]. Đây là các bước để tạo ra nó
- Chọn một yếu tố từ đầu vào i. e. tập con[len] = S[pos]. Chúng tôi có thể quyết định đưa nó vào tập hợp con hiện tại hay không
- Đệ quy tạo thành tập hợp con bao gồm nó i. e. allSubsets[pos+1, len+1, subset]
- Đệ quy tạo thành tập hợp con không bao gồm nó i. e. allSubsets[pos+1, len, subsets]
- Đảm bảo tạo từng bộ một lần
Mã giả
int S[N]
void allSubsets[int pos, int len, int[] subset]
{
if[pos == N]
{
print[subset]
return
}
// Try the current element in the subset.
subset[len] = S[pos]
allSubsets[pos+1, len+1, subset]
// Skip the current element.
allSubsets[pos+1, len, subset]
}Phân tích độ phức tạp
Ở đây chúng tôi đang tạo mọi tập hợp con bằng cách sử dụng đệ quy. Tổng số tập hợp con của một tập hợp có kích thước n = 2^n đã cho
Thời gian phức tạp. O[2^n]
Độ phức tạp không gian. O[n] cho tập hợp con mảng bổ sung
Ý tưởng quan trọng để suy nghĩ
- Tại sao chúng ta theo dõi cả hai trường hợp khi chúng ta chọn phần tử và khi chúng ta không chọn phần tử?
- Bạn có thể viết mối quan hệ lặp lại cho thuật toán trên không?
- Bạn có thể nghĩ ra một số cách khác để thực hiện giải pháp này không?
- Chúng ta có thể giải quyết vấn đề này bằng ngăn xếp không?
- Xác định các vấn đề có thể được giải quyết bằng cách sử dụng phương pháp tương tự
2. Phương pháp mặt nạ bit
Ý tưởng giải pháp
Vì vậy, thay vì sử dụng một mảng, chúng ta chỉ có thể sử dụng một số nguyên duy nhất có các bit riêng lẻ đại diện cho các mục của mảng. Vì vậy, bit thứ i là 1 hoặc 0 vì mục nhập thứ i của mảng là đúng hay sai. Đây thường được gọi là phương pháp mặt nạ bit, thực sự hữu ích để giải quyết các loại vấn đề khác. [Nghĩ. ]
Để hiểu quay lui là gì, hãy quay lại những điều cơ bản của các lệnh gọi hàm. Trong một lời gọi hàm, có hàm được gọi và hàm gọi. Vì vậy, trong đoạn mã dưới đây,
gen[A,0,sz]là hàm gọi và
gen[vector &A,int k,int n]là hàm được gọi
Giả sử hàm gọi nằm trong hàm chính và tất nhiên hàm được gọi được xác định bên ngoài hàm chính. Vì quá trình thực thi luôn bắt đầu từ chức năng chính, nên quá trình thực thi chương trình sẽ đến chức năng gọi trước và sau khi đạt đến, quá trình thực thi sẽ rời khỏi chức năng chính và tiếp tục thực thi trong chức năng được gọi [sử dụng trình gỡ lỗi để xem hoạt động của hành vi này]. Bây giờ, khi trình biên dịch đã hoàn thành việc thực thi các mã trong hàm được gọi, điều khiển sẽ quay trở lại hàm gọi;
Giải thích ở trên có thể không mang lại sự hiểu biết đầy đủ về khái niệm này bởi vì ở đó chúng ta đã xử lý tình huống chỉ có một lệnh gọi hàm và định nghĩa hàm của hàm được gọi nằm ngoài hàm gọi
Bây giờ chúng ta hãy hiểu rõ hơn về quay lui - điều cần thiết để hiểu cách tạo tập hợp con bằng cách sử dụng đệ quy. Một hàm có khả năng gọi chính nó – hàm như vậy được gọi là hàm đệ quy. Bao nhiêu lần một chức năng có thể gọi chính nó? . Bây giờ giả sử chúng ta có một biến gọi là k được khởi tạo bằng 0 và chúng ta nói rằng một hàm sẽ tiếp tục gọi chính nó trong khi k