Leetcode 40 Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

• Soruda bize candidates listesi içinde sayılar ve bir target sayı veriliyor.Bu liste içindeki sayıları toplayarak target bulmamız isteniyor.
• Daha önce çözülen 39. probleme benzer şekilde çözülebilir.Burada dikkat edilmesi gereken bize verilen listede aynı sayıdan birden fazla olabilir ve bulduğumuz kombinasyonlar benzersiz olmalı.
• Örneğin listede 2 tane 1 var [1,2,3,1] bizden 4 isteniyor.[1,3] ve [3,1] sonuç listemizde olamaz sadece biri olabilir.
• İlk olarak listeyi küçükten büyüğe sıralarız bu şekilde eşit sayılar yanyana gelmiş olur.
• Sonrasında prev diye bir değişken oluşturup indexteki sayının bir önceki sayıyı burada tutarız.Bu sayede elimizdeki sayı ile önceki sayıyı karşılaştırırız aynı ise atlarız.
• Tabi burada başka bir pratik çözüm listeyi sıraldıktan sonra set bir listeye atmak.Set listelerde aynı değerden tutulmadığı için işimizi kolaylaştırır.
• Devamında arama için oluşturduğumuz backtrack fonksiyonunu rekürsif olarak çağrırız.
• Her çağrıda kontrollerimizi yaparız.
• Bir önceki örnekten farklı olarak kombinasyona eklediğimiz sayıları targettan çıkararak targetı sıfırlamaya çalışırız.

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        
        res = []
        
        def backtrack(cur,pos,target):
            if target==0:
                res.append(cur.copy())
            if target <= 0:
                return
            
            prev = -1
            
            for i in range(pos,len(candidates)):
                if candidates[i] == prev:
                    continue
                
                cur.append(candidates[i])
                backtrack(cur,i+1,target - candidates[i])
                cur.pop()
                prev = candidates[i]
        
        backtrack([], 0, target)
        return res