Tập con (Subsets) trong Python

Giả sử ta có một tập hợp số; ta phải sinh tất cả các tập con có thể của tập hợp đó. Điều này còn gọi là tập lũy thừa (power set). Ví dụ, nếu tập hợp là [1,2,3], tập lũy thừa sẽ là [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]].

Các bước:

• Giải quyết bằng đệ quy. Hàm đệ quy tên solve(), nhận tập số (nums), tập tạm (temp), kết quả (res) và chỉ số (index).

• Hàm solve() hoạt động như sau:

  • Nếu index == độ dài nums, tạo list giống temp, chèn vào res và trả về.
  • temp[index] := 0.
  • Gọi solve(nums, temp, res, index+1).
  • temp[index] := 1.
  • Gọi solve(nums, temp, res, index+1).

• Hàm chính:

  • res := list rỗng.
  • Tạo temp list kích thước bằng nums, điền 0.
  • Gọi solve(nums, temp, res, 0).
  • main_res := list rỗng.
  • Với mỗi list trong temp_res:
    • temp := list rỗng.
    • Với i từ 0 đến độ dài list:
      • Nếu list[i] == 1, chèn nums[i] vào temp.
    • Chèn temp vào main_res.
  • Trả về main_res.

Ví dụ

class Solution(object):
    def subsets(self, nums):
        ket_qua_tam = []
        self.subsets_util(nums, [0 for i in range(len(nums))], ket_qua_tam, 0)
        ket_qua_chinh = []
        for lists in ket_qua_tam:
            temp = []
            for i in range(len(lists)):
                if lists[i] == 1:
                    temp.append(nums[i])
            ket_qua_chinh.append(temp)
        return ket_qua_chinh
    
    def subsets_util(self, nums, temp, ket_qua, chi_so):
        if chi_so == len(nums):
            ket_qua.append([i for i in temp])
            return
        temp[chi_so] = 0
        self.subsets_util(nums, temp, ket_qua, chi_so + 1)
        temp[chi_so] = 1
        self.subsets_util(nums, temp, ket_qua, chi_so + 1)

ob1 = Solution()
print(ob1.subsets([1,2,3,4]))

Đầu vào

[1,2,3,4]

Đầu ra

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