Cho một số nguyên dương n, chúng ta phải in tất cả các tập con của tập hợp {1, 2, 3, 4,… n} mà không sử dụng bất kỳ mảng hoặc vòng lặp nào.
Giống như chúng tôi đã đưa ra bất kỳ số nào, giả sử là 3 s, chúng tôi phải in tất cả các tập con trong tập hợp {1, 2, 3} sẽ là {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3} {}.
Nhưng chúng ta phải làm điều này mà không sử dụng bất kỳ vòng lặp hoặc một mảng nào. Vì vậy, chỉ có đệ quy là cách khả thi để giải quyết loại vấn đề này mà không cần sử dụng bất kỳ mảng hoặc vòng lặp nào.
Ví dụ
Input: 3
Output: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
Explanation: The set will be {1 2 3} from which we will find the subsets
Input: 4
Output: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ } Phương pháp tiếp cận mà chúng tôi sẽ sử dụng để giải quyết vấn đề đã cho -
- Bắt đầu từ num =2 ^ n -1 đến 0.
- Xem xét biểu diễn nhị phân của num với n số bit.
- Bắt đầu từ bit ngoài cùng bên trái đại diện cho 1, bit thứ hai đại diện cho 2, v.v. cho đến bit thứ n đại diện cho n.
- In số tương ứng với bit nếu nó được đặt.
- Thực hiện các bước trên cho tất cả các giá trị của num cho đến khi nó bằng 0.
Hãy hiểu chi tiết cách thức hoạt động của cách tiếp cận đã nêu bằng cách sử dụng một ví dụ đơn giản -
Giả sử đầu vào n =3, do đó, sự cố bắt đầu từ num =2 ^ 3 - 1 =7
- Biểu diễn nhị phân của 7 ⇒
| 1 | 1 | 1 |
- Tập hợp con tương ứng ⇒
| 1 | 2 | 3 |
Trừ 1 cho num; num =6
- Biểu diễn nhị phân của 6 ⇒
| 1 | 1 | 0 |
- Tập hợp con tương ứng ⇒
| 1 | 2 | |
Trừ 1 cho num; num =5
- Biểu diễn nhị phân của 5 ⇒
| 1 | 0 | 1 |
- Tập hợp con tương ứng ⇒
| 1 | | 3 |
Trừ 1 cho num; num =4
- Biểu diễn nhị phân của 4 ⇒
| 1 | 0 | 0 |
- Tập hợp con tương ứng ⇒
| 1 | | |
Tương tự như vậy, chúng tôi sẽ lặp lại cho đến khi num =0 và in tất cả các tập hợp con.
Thuật toán
Start
Step 1 → In function int subset(int bitn, int num, int num_of_bits)
If bitn >= 0
If (num & (1 << bitn)) != 0
Print num_of_bits - bitn
subset(bitn - 1, num, num_of_bits);
Else
Return 0
Return 1
Step 2 → In function int printSubSets(int num_of_bits, int num)
If (num >= 0)
Print "{ "
Call function subset(num_of_bits - 1, num, num_of_bits)
Print "}"
Call function printSubSets(num_of_bits, num - 1)
Else
Return 0
Return 1
Step 3 → In function int main()
Declare and initialize int n = 4
Call fucntionprintSubSets(n, (int) (pow(2, n)) -1)
Stop Ví dụ
#include <stdio.h>
#include <math.h>
// This function recursively prints the
// subset corresponding to the binary
// representation of num.
int subset(int bitn, int num, int num_of_bits) {
if (bitn >= 0) {
// Print number in given subset only
// if the bit corresponding to it
// is set in num.
if ((num & (1 << bitn)) != 0) {
printf("%d ", num_of_bits - bitn);
}
// Check the next bit
subset(bitn - 1, num, num_of_bits);
}
else
return 0;
return 1;
}
//function to print the subsets
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
// Printint the subsets corresponding to
// the binary representation of num.
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
// recursively calling the function to
// print the next subset.
printSubSets(num_of_bits, num - 1);
}
else
return 0;
return 1;
}
//main program
int main() {
int n = 4;
printSubSets(n, (int) (pow(2, n)) -1);
} Đầu ra
{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }