今天是紀錄LeetCode解題的第四十天

第四十題題目：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.

給定一組候選數字candidate和目標整數target，回傳所有滿足所選數字總和為target的唯一組合，組合中的每個數字只能使用一次

注意：解決方案集合中不得包含重複的組合

解題思路

這題和39題很類似，不同的地方在於39題的candidate都是不同數字且每個數字可重複使用，而40題的candidate可能包含重複數字，且每個數字只能使用一次，所以為了避免重複的數字會產生重複的組合，我們可以先將candidate做排序，且在回溯法的過程中，判斷該層(start)的迭代(i)是否i > start(以範例2的[1,2,2,2,5]說明，我們會先找到[1,2,2]的組合符合target(此時start = 2)，這時候回溯變成[1,2]，且i迭代變成3，該情況就符合i > start)且還需判斷相鄰兩數字相同(i = 3時，我們可以知道索引2和3的值都是2)，上述皆符合我們就直接continue，避免再重複找到[1,2,2]的組合，而因為每個數字只能使用一次，所以在遞迴時是傳遞i+1(一開始i=0選擇數字1，再次呼叫遞迴傳遞i+1選擇數字2)

程式碼

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []

        def backtracking(start,path,total):
            if total == target:
                result.append(path[:])
                return
            elif total > target:
                return
            else:
                for i in range(start,len(candidates)):
                    if i > start and candidates[i] == candidates[i-1]:
                        continue
                    path.append(candidates[i])
                    backtracking(i+1,path,total+candidates[i])
                    path.pop()

        backtracking(0,[],0)
        return result

執行過程(candidates = [2,5,2,1,2], target = 5)

以上是執行過程，start可以想成是主要要找和它可以做組合的數字，start = 0表示主要找可以和1組合的，而i可以想成去找能和主要數字配對的