LeetCode 筆記 - 40. Combination Sum II

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

給一個數列與目標數，請從數列找出相加的組合等於目標數，每個數字只能用一次

解題思維

如果沒解過第一題可以看這篇 LeetCode 筆記 - 39. Combination Sum

這題一樣是用 Depth First Search 跑一次就可以了

其中這裡有用到一個技巧來避開重複的組合

1 2	if i > last_index + 1 and candidates[i] == candidates[i- 1]: continue

在這篇筆記有比較詳細的解釋 LeetCode 筆記 - 47. Permutations II

最後的小技巧就是先 Sorting，來跳過一些計算

程式碼

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        
        if sum(candidates) < target:
            return []
        
        candidates.sort()
        candidate_size = len(candidates)
        
        self.result = []
        def dfs(last_index, result, count):
            if count == target:
                self.result.append(result)
                return
            
            for i in range(last_index + 1, candidate_size):
                if count + candidates[i] > target:
                    break
                    
                if i > last_index + 1 and candidates[i] == candidates[i- 1]:
                    continue
                
                dfs(i, result + [candidates[i]], count + candidates[i])
        
        dfs(-1, [], 0)
        
        return self.result

😎

解題思維

程式碼

也許你也會想看看