Leetcode 39 Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

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

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

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

• Soruda bize candidates listesi içinde sayılar ve bir target sayı veriliyor.Bu liste içindeki sayıları toplayarak target bulmamız isteniyor.
• Yukarıdaki resimde algoritma mantığı görülebilir.
• Elimizde [2,3,6,7] şeklinde bir liste ve bizden 7 toplamını bulmamız istensin.Rekursif olarak çağıracağımız fonksiyon ile istenen kombinasyonları arayalım.
• Resimde görüleceği gibi fonksiyon ilk çağrıldığında [2] içeren ve 2 içermeyen [] iki liste oluşur.
• [2] olan liste için fonksiyon tekrar çağrıldığında [2,2] ve [2] şeklinde bir alt dal oluşur.
• Buradaki amaç aynı listelerin oluşmaması için kullanılan sayının tekrar aynı şekilde kullanılmamasıdır.

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        
        def dfs(i, cur, total):
            if total == target: #liste toplamı target eşit ise listeyi res at ve return
                res.append(cur.copy())
                return
            if i>= len(candidates) or total > target: # elindeki sayılar biterse yada toplam targettan 
                return                                #büyük olursa return
            
            cur.append(candidates[i]) #index sayıyı listeye ekle-toplama ekle ve dfs aynı index ile çağır
            dfs(i, cur, total + candidates[i])  
            cur.pop()                 #index sayıyı listeden çıkar ve dfs indexi 1 arttırarak çağır
            dfs(i + 1, cur, total)    
        
        dfs(0,[],0)
        return res