Tìm Tất Cả Các Tập Con Của Một Tập Hợp Trong JavaScript

Để tìm tất cả các tập con của một tập hợp trong JavaScript, bạn có thể sử dụng phương pháp đệ quy hoặc phương pháp duyệt tổ hợp. Một trong những cách tiếp cận phổ biến là sử dụng backtracking để sinh ra tất cả các tập con của tập hợp.

Mã Nguồn:

function subsets(nums) {
    let result = [];

    function backtrack(start, currentSubset) {
        result.push([...currentSubset]);

        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            backtrack(i + 1, currentSubset);
            currentSubset.pop();
        }
    }

    backtrack(0, []);
    return result;
}

// Ví dụ kiểm tra
console.log(subsets([1, 2, 3]));
/*
[
  [],       [ 1 ],
  [ 1, 2 ], [ 1, 2, 3 ],
  [ 1, 3 ], [ 2 ],
  [ 2, 3 ], [ 3 ]
]
*/

Giải Thích:

1. Hàm Backtrack:

   • Hàm backtrack được sử dụng để sinh ra các tập con bằng cách thêm từng phần tử vào tập con hiện tại và gọi đệ quy để tiếp tục thêm các phần tử khác.

2. Thêm Tập Con Hiện Tại vào Kết Quả:

   • Mỗi khi gọi hàm backtrack, tập con hiện tại (currentSubset) được sao chép và thêm vào mảng result.

3. Duyệt Qua Các Phần Tử:

   • Vòng lặp for duyệt qua các phần tử từ vị trí start đến cuối mảng nums.
   • Từng phần tử được thêm vào currentSubset và hàm backtrack được gọi đệ quy với vị trí bắt đầu mới (i + 1).
   • Sau khi đệ quy hoàn thành, phần tử cuối cùng được loại bỏ (backtracking) để thử các tổ hợp khác.

Tổng Quan:

• Backtracking: Kỹ thuật đệ quy mạnh mẽ, hữu ích trong việc sinh ra các tổ hợp hoặc hoán vị.
• Độ Phức Tạp Thời Gian: O(2^n), do có 2^n tập con có thể có từ một tập hợp n phần tử.
• Ứng Dụng: Thích hợp cho các bài toán tổ hợp và sinh tập con trong các ngôn ngữ lập trình.

Ví Dụ Thực Tế:

console.log(subsets([1, 2, 3]));
/*
[
  [],       [ 1 ],
  [ 1, 2 ], [ 1, 2, 3 ],
  [ 1, 3 ], [ 2 ],
  [ 2, 3 ], [ 3 ]
]
*/

Trong ví dụ trên, tập hợp [1, 2, 3] có tất cả các tập con được sinh ra, bao gồm cả tập rỗng.