子集和問題¶

無重複元素的情況¶

Question

給定一個正整數陣列 nums 和一個目標正整數 target ，請找出所有可能的組合，使得組合中的元素和等於 target 。給定陣列無重複元素，每個元素可以被選取多次。請以串列形式返回這些組合，串列中不應包含重複組合。

例如，輸入集合 \(\{3, 4, 5\}\) 和目標整數 \(9\) ，解為 \(\{3, 3, 3\}, \{4, 5\}\) 。需要注意以下兩點。

輸入集合中的元素可以被無限次重複選取。
子集不區分元素順序，比如 \(\{4, 5\}\) 和 \(\{5, 4\}\) 是同一個子集。

參考全排列解法¶

類似於全排列問題，我們可以把子集的生成過程想象成一系列選擇的結果，並在選擇過程中實時更新“元素和”，當元素和等於 target 時，就將子集記錄至結果串列。

而與全排列問題不同的是，本題集合中的元素可以被無限次選取，因此無須藉助 selected 布林串列來記錄元素是否已被選擇。我們可以對全排列程式碼進行小幅修改，初步得到解題程式碼：

[file]{subset_sum_i_naive}-[class]{}-[func]{subset_sum_i_naive}

向以上程式碼輸入陣列 \([3, 4, 5]\) 和目標元素 \(9\) ，輸出結果為 \([3, 3, 3], [4, 5], [5, 4]\) 。雖然成功找出了所有和為 \(9\) 的子集，但其中存在重複的子集 \([4, 5]\) 和 \([5, 4]\) 。

這是因為搜尋過程是區分選擇順序的，然而子集不區分選擇順序。如下圖所示，先選 \(4\) 後選 \(5\) 與先選 \(5\) 後選 \(4\) 是不同的分支，但對應同一個子集。

為了去除重複子集，一種直接的思路是對結果串列進行去重。但這個方法效率很低，有兩方面原因。

當陣列元素較多，尤其是當 target 較大時，搜尋過程會產生大量的重複子集。
比較子集（陣列）的異同非常耗時，需要先排序陣列，再比較陣列中每個元素的異同。

重複子集剪枝¶

我們考慮在搜尋過程中透過剪枝進行去重。觀察下圖，重複子集是在以不同順序選擇陣列元素時產生的，例如以下情況。

當第一輪和第二輪分別選擇 \(3\) 和 \(4\) 時，會生成包含這兩個元素的所有子集，記為 \([3, 4, \dots]\) 。
之後，當第一輪選擇 \(4\) 時，則第二輪應該跳過 \(3\) ，因為該選擇產生的子集 \([4, 3, \dots]\) 和第 1. 步中生成的子集完全重複。

在搜尋過程中，每一層的選擇都是從左到右被逐個嘗試的，因此越靠右的分支被剪掉的越多。

前兩輪選擇 \(3\) 和 \(5\) ，生成子集 \([3, 5, \dots]\) 。
前兩輪選擇 \(4\) 和 \(5\) ，生成子集 \([4, 5, \dots]\) 。
若第一輪選擇 \(5\) ，則第二輪應該跳過 \(3\) 和 \(4\) ，因為子集 \([5, 3, \dots]\) 和 \([5, 4, \dots]\) 與第 1. 步和第 2. 步中描述的子集完全重複。

總結來看，給定輸入陣列 \([x_1, x_2, \dots, x_n]\) ，設搜尋過程中的選擇序列為 \([x_{i_1}, x_{i_2}, \dots, x_{i_m}]\) ，則該選擇序列需要滿足 \(i_1 \leq i_2 \leq \dots \leq i_m\) ，不滿足該條件的選擇序列都會造成重複，應當剪枝。

程式碼實現¶

為實現該剪枝，我們初始化變數 start ，用於指示走訪起始點。當做出選擇 \(x_{i}\) 後，設定下一輪從索引 \(i\) 開始走訪。這樣做就可以讓選擇序列滿足 \(i_1 \leq i_2 \leq \dots \leq i_m\) ，從而保證子集唯一。

除此之外，我們還對程式碼進行了以下兩項最佳化。

在開啟搜尋前，先將陣列 nums 排序。在走訪所有選擇時，當子集和超過 target 時直接結束迴圈，因為後邊的元素更大，其子集和一定超過 target 。
省去元素和變數 total ，透過在 target 上執行減法來統計元素和，當 target 等於 \(0\) 時記錄解。

[file]{subset_sum_i}-[class]{}-[func]{subset_sum_i}

下圖所示為將陣列 \([3, 4, 5]\) 和目標元素 \(9\) 輸入以上程式碼後的整體回溯過程。

考慮重複元素的情況¶

Question

給定一個正整數陣列 nums 和一個目標正整數 target ，請找出所有可能的組合，使得組合中的元素和等於 target 。給定陣列可能包含重複元素，每個元素只可被選擇一次。請以串列形式返回這些組合，串列中不應包含重複組合。

相比於上題，本題的輸入陣列可能包含重複元素，這引入了新的問題。例如，給定陣列 \([4, \hat{4}, 5]\) 和目標元素 \(9\) ，則現有程式碼的輸出結果為 \([4, 5], [\hat{4}, 5]\) ，出現了重複子集。

造成這種重複的原因是相等元素在某輪中被多次選擇。在下圖中，第一輪共有三個選擇，其中兩個都為 \(4\) ，會產生兩個重複的搜尋分支，從而輸出重複子集；同理，第二輪的兩個 \(4\) 也會產生重複子集。

相等元素剪枝¶

為解決此問題，我們需要限制相等元素在每一輪中只能被選擇一次。實現方式比較巧妙：由於陣列是已排序的，因此相等元素都是相鄰的。這意味著在某輪選擇中，若當前元素與其左邊元素相等，則說明它已經被選擇過，因此直接跳過當前元素。

與此同時，本題規定每個陣列元素只能被選擇一次。幸運的是，我們也可以利用變數 start 來滿足該約束：當做出選擇 \(x_{i}\) 後，設定下一輪從索引 \(i + 1\) 開始向後走訪。這樣既能去除重複子集，也能避免重複選擇元素。

程式碼實現¶

[file]{subset_sum_ii}-[class]{}-[func]{subset_sum_ii}

下圖展示了陣列 \([4, 4, 5]\) 和目標元素 \(9\) 的回溯過程，共包含四種剪枝操作。請你將圖示與程式碼註釋相結合，理解整個搜尋過程，以及每種剪枝操作是如何工作的。