สมมติว่าเรามีชุดหมายเลขผู้สมัคร (องค์ประกอบทั้งหมดไม่ซ้ำกัน) และหมายเลขเป้าหมาย เราต้องหาชุดค่าผสมที่ไม่ซ้ำกันทั้งหมดในผู้สมัครโดยที่หมายเลขของผู้สมัครรวมเข้ากับเป้าหมายที่กำหนด โดยสามารถเลือกหมายเลขซ้ำได้จากผู้สมัครไม่จำกัดจำนวนครั้ง ดังนั้นหากองค์ประกอบเป็น [2,3,6,7] และค่าเป้าหมายคือ 7 ผลลัพธ์ที่เป็นไปได้จะเป็น [[7], [2,2,3]]
ให้เราดูขั้นตอน -
-
เราจะแก้ปัญหานี้ในลักษณะเรียกซ้ำ ฟังก์ชันเรียกซ้ำมีชื่อเป็น Solve() การดำเนินการนี้ใช้อาร์เรย์ในการจัดเก็บผลลัพธ์ แผนที่เดียวเพื่อเก็บบันทึก ค่าเป้าหมาย และรายการองค์ประกอบที่แตกต่างกัน เริ่มแรก res array และ map ว่างเปล่า วิธีการแก้จะทำงานดังนี้ -
- ถ้าเป้าหมายเป็น 0 แล้ว
- temp :=รายการองค์ประกอบที่มีอยู่ในรายการ
- temp1 :=temp จากนั้นเรียงลำดับ temp
- ถ้า temp ไม่ได้อยู่ในแผนที่ ให้แทรก temp ลงในแผนที่และตั้งค่าเป็น 1 แทรก temp ลงใน res
- คืนสินค้า
- ถ้าอุณหภูมิ <0 ให้กลับ
- สำหรับ x ในช่วง i ถึงความยาวของรายการองค์ประกอบ
- แทรกองค์ประกอบ[x] ลงในกระแส
- แก้(องค์ประกอบ เป้าหมาย – องค์ประกอบ[x], res, แผนที่, i, ปัจจุบัน)
- ลบองค์ประกอบจากรายการปัจจุบันจากดัชนี (ความยาวของกระแส – 1)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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)) อินพุต
[2,3,6,7,8] 10
ผลลัพธ์
[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]
