สมมติว่าเรามีชุดตัวเลขหล보 (candidate numbers) ที่ไม่ซ้ำกัน และตัวเลขเป้าหมาย (target) เราต้องหาการจัดหมู่ที่ไม่ซ้ำกันทั้งหมดใน candidates ที่ผลรวมเท่ากับ target ตัวเลขเดียวกันสามารถเลือกใช้ได้ไม่จำกัดครั้ง ตัวอย่าง: candidates = [2,3,6,7] และ target = 7 ผลลัพธ์คือ [[7], [2,2,3]]
ขั้นตอนการทำงาน (Recursive Backtracking)
- สร้างฟังก์ชัน recursive ชื่อ
solve()รับพารามิเตอร์: อาร์เรย์เก็บผลลัพธ์, map สำหรับตรวจสอบซ้ำ, ค่า target, และลิสต์องค์ประกอบที่ไม่ซ้ำกัน - ถ้า
target == 0:- สร้าง
tempจากลิสต์ปัจจุบัน เรียงลำดับ แปลงเป็น tuple - ถ้ายังไม่มีใน map ให้เพิ่มลง map และเพิ่มลงผลลัพธ์
- คืนค่า
- สร้าง
- ถ้า
target < 0ให้คืนค่า - วนลูป
xจากiถึงความยาวของลิสต์องค์ประกอบ:- เพิ่ม
elements[x]ลงในลิสต์ปัจจุบัน - เรียก
solve(elements, target - elements[x], res, map, i, current) - ลบองค์ประกอบสุดท้ายออกจากลิสต์ปัจจุบัน
- เพิ่ม
ตัวอย่างโค้ด
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]]
