Tổng tổ hợp trong Python

Giả sử chúng ta có một tập hợp các số ứng viên (tất cả các phần tử duy nhất) và một số mục tiêu. Chúng ta phải tìm tất cả các tổ hợp duy nhất trong ứng viên sao cho tổng các số ứng viên bằng mục tiêu cho trước. Cùng một số có thể được chọn từ ứng viên vô số lần. Ví dụ, nếu các phần tử là [2,3,6,7] và giá trị mục tiêu là 7, thì đầu ra có thể là [[7], [2,2,3]].

Các bước thực hiện

• Chúng ta sẽ giải quyết bằng phương pháp đệ quy. Hàm đệ quy tên là solve(). Nó nhận một mảng lưu kết quả, một bản đồ để ghi nhận, giá trị mục tiêu và danh sách các phần tử riêng biệt. Ban đầu mảng kết quả và bản đồ rỗng. Hàm solve hoạt động như sau:
• Nếu mục tiêu bằng 0:
  • temp := danh sách các phần tử hiện có trong danh sách hiện tại.
  • temp1 := temp, sau đó sắp xếp temp.
  • Nếu temp không có trong bản đồ, chèn temp vào bản đồ với giá trị 1, chèn temp1 vào kết quả.
  • Trả về.
• Nếu mục tiêu < 0, trả về.
• Với x từ i đến độ dài danh sách phần tử:
  • Chèn elements[x] vào danh sách hiện tại.
  • Gọi đệ quy solve(elements, target - elements[x], res, map, i, current).
  • Xóa phần tử khỏi danh sách hiện tại từ chỉ số (độ dài current - 1).

Ví dụ minh họa

class Solution(object):
    def combinationSum(self, candidates, target):
        result = []
        unique = {}
        candidates = list(set(candidates))
        self.solve(candidates, target, result, unique)
        return result

    def solve(self, candidates, target, result, unique, i=0, current=[]):
        if target == 0:
            temp = [i for i in current]
            temp1 = temp
            temp.sort()
            temp = tuple(temp)
            if temp not in unique:
                unique[temp] = 1
                result.append(temp1)
            return
        if target < 0:
            return
        for x in range(i, len(candidates)):
            current.append(candidates[x])
            self.solve(candidates, target - candidates[x], result, unique, i, current)
            current.pop(len(current)-1)

ob1 = Solution()
print(ob1.combinationSum([2,3,6,7,8], 10))

Đầu vào

[2,3,6,7,8] 10

Đầu ra

[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]