#39. Combination Sum

題目描述

給你一個整數陣列candidates，陣列中每個數值都是唯一的，以及一個目標整數target，請找出數字加總起來會等於target的組合，回傳所有不同的唯一組合。

你可以以不同的順序回傳組合。

candidates中同樣的數字可以被重複選擇無限多次。兩個組合之間是否是唯一的取決於兩個組合中最少有一個數字是不同的。

測試案例的唯一組合數量答案會被限制在150之下。

限制條件

1. 1 <= candidates.length <= 30
2. 2 <= candidates[i] <= 40
3. candidates中每個數值都是唯一的。
4. 1 <= target <= 40

解題思路

數字的加總比較好處理，而比較需要思考的是如何排除重複的組合。

舉例來說： candidates = [2,3,4,5]
target = 8
答案會有： [2,2,2,2]、[2,2,4]、[3,5]
重複的組合像是[2,4,2]、[4,2,2]、[5,3]等不應該被加入到答案中。

這個部分的處理方式就是每一次數字挑選只能從自己開始向後挑，不能往前挑，就可以避免組合出重複的答案。

Solution

執行步驟如下：

1. 從candidates中選取元素。
2. 將target減去選取的元素獲得新的target數值newTarget，newTarget會有以下三種情形。
   1. 等於0：代表找到答案了，將當前選取的元素放入ans中之後，繼續嘗試其他選項。
   2. 小於0：代表當前選取的元素行不通，繼續嘗試其他選項。
   3. 大於0：代表未滿足條件，將當前獲得的新的newTarget，已經選取的元素newPicked，以及刪去不需要元素的candidates放入到下一輪進行重複的動作。
3. 處理完後得到答案。

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        var ans = new List<IList<int>>();        
        Helper(candidates, target,new List<int>(), ans);
        return ans;
    }
    public void Helper(int[] candidates, int target, List<int> picked,List<IList<int>> ans){
        for(int i=0;i<candidates.Length;i++){
            int newTarget = target - candidates[i];
            if(newTarget==0){
                var newPicked = new List<int>(picked);
                newPicked.Add(candidates[i]);
                ans.Add(newPicked);
                continue;
            }
            if(newTarget<0) continue;
            if(newTarget>0){
                var newPicked = new List<int>(picked);
                newPicked.Add(candidates[i]);
                Helper(candidates.Skip(i).ToArray(),newTarget,newPicked,ans);
            }
        }
    }
}

複雜度分析：

• 時間複雜度：如果所有可能都嘗試的話，嘗試時間會是n^2，但這題要避免重複可能，因此會刪去candidates的選項，但最差的情況下仍然會需要一半左右的嘗試，實際花上的時間是n*(n-1)/2，時間複雜度為O(n^2)。
• 空間複雜度：Helper()一次占用的空間最多為candidates.length，因此空間複雜度為O(n)。

學習重點

• Backtracking