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ử là duy nhất) và một số mục tiêu. Chúng tôi phải tìm tất cả các kết hợp duy nhất trong các ứng cử viên mà số ứng viên tổng hợp thành mục tiêu đã cho. Số lần lặp lại giống nhau có thể được chọn từ các ứng viên không giới hạn số lần. Vì vậy, nếu các phần tử là [2,3,6,7] và giá trị đích là 7, thì đầu ra có thể sẽ là [[7], [2,2,3]]
Hãy để chúng tôi xem các bước -
-
Chúng tôi sẽ giải quyết điều này theo cách đệ quy. Hàm đệ quy được đặt tên là giải quyết (). Điều này có một mảng để lưu trữ kết quả, một bản đồ để lưu giữ các bản ghi, giá trị đích và danh sách các phần tử riêng biệt. Ban đầu mảng res và bản đồ trống. Phương thức giải sẽ hoạt động như bên dưới -
- nếu mục tiêu là 0, thì
- temp:=danh sách các phần tử có trong danh sách
- temp1:=temp, sau đó sắp xếp nhiệt độ
- nếu tạm thời không có trong bản đồ, hãy chèn tạm thời vào bản đồ và đặt giá trị là 1, chèn tạm thời vào res
- trở lại
- nếu nhiệt độ <0, thì trả về
- cho x trong phạm vi i đến độ dài của danh sách phần tử,
- chèn các phần tử [x] vào hiện tại
- giải quyết (các phần tử, mục tiêu - các phần tử [x], res, map, i, current)
- xóa phần tử khỏi danh sách hiện tại khỏi chỉ mục (độ dài của hiện tại - 1)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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]]