C++子集和問題

無重復元素的情況

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

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

1.   參考全排列解法

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

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

subset_sum_i_naive.cpp

/* 回溯算法：子集和 I */
void backtrack(vector<int> &state, int target, int total, vector<int> &choices, vector<vector<int>> &res) {
    // 子集和等于 target 時，記錄解
    if (total == target) {
        res.push_back(state);
        return;
    }
    // 遍歷所有選擇
    for (size_t i = 0; i < choices.size(); i++) {
        // 剪枝：若子集和超過 target ，則跳過該選擇
        if (total + choices[i] > target) {
            continue;
        }
        // 嘗試：做出選擇，更新元素和 total
        state.push_back(choices[i]);
        // 進行下一輪選擇
        backtrack(state, target, total + choices[i], choices, res);
        // 回退：撤銷選擇，恢復到之前的狀態(tài)
        state.pop_back();
    }
}

/* 求解子集和 I（包含重復子集） */
vector<vector<int>> subsetSumINaive(vector<int> &nums, int target) {
    vector<int> state;       // 狀態(tài)（子集）
    int total = 0;           // 子集和
    vector<vector<int>> res; // 結果列表（子集列表）
    backtrack(state, target, total, nums, res);
    return res;
}

向以上代碼輸入數(shù)組 $[3,4,5]$ 和目標元素 $9$ ，輸出結果為 $[3,3,3],[4,5],[5,4]$ 。雖然成功找出了所有和為 $9$ 的子集，但其中存在重復的子集 $[4,5]$ 和 $[5,4]$ 。

這是因為搜索過程是區(qū)分選擇順序的，然而子集不區(qū)分選擇順序。如圖 13-10 所示，先選 $4$ 后選 $5$ 與先選 $5$ 后選 $4$ 是兩個不同的分支，但兩者對應同一個子集。

圖 13-10   子集搜索與越界剪枝

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

• 當數(shù)組元素較多，尤其是當 target 較大時，搜索過程會產生大量的重復子集。
• 比較子集（數(shù)組）的異同非常耗時，需要先排序數(shù)組，再比較數(shù)組中每個元素的異同。

2.   重復子集剪枝

我們考慮在搜索過程中通過剪枝進行去重。觀察圖 13-11 ，重復子集是在以不同順序選擇數(shù)組元素時產生的，例如以下情況。

1. 當?shù)谝惠喓偷诙喎謩e選擇 $3$ 和 $4$ 時，會生成包含這兩個元素的所有子集，記為 $[3,4,\dots ]$ 。
2. 之后，當?shù)谝惠嗊x擇 $4$ 時，則第二輪應該跳過 $3$ ，因為該選擇產生的子集 $[4,3,\dots ]$ 和 1. 中生成的子集完全重復。

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

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

圖 13-11   不同選擇順序導致的重復子集

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

3.   代碼實現(xiàn)

為實現(xiàn)該剪枝，我們初始化變量 start ，用于指示遍歷起點。當做出選擇 $x_i$ 后，設定下一輪從索引 $i$ 開始遍歷。這樣做就可以讓選擇序列滿足 $i_1\le i_2\le ?\le i_m$ ，從而保證子集唯一。

除此之外，我們還對代碼進行了以下兩項優(yōu)化。

• 在開啟搜索前，先將數(shù)組 nums 排序。在遍歷所有選擇時，當子集和超過 target 時直接結束循環(huán)，因為后邊的元素更大，其子集和都一定會超過 target 。
• 省去元素和變量 total ，通過在 target 上執(zhí)行減法來統(tǒng)計元素和，當 target 等于 $0$ 時記錄解。

  subset_sum_i.cpp
  
  /* 回溯算法：子集和 I */
  void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
      // 子集和等于 target 時，記錄解
      if (target == 0) {
          res.push_back(state);
          return;
      }
      // 遍歷所有選擇
      // 剪枝二：從 start 開始遍歷，避免生成重復子集
      for (int i = start; i < choices.size(); i++) {
          // 剪枝一：若子集和超過 target ，則直接結束循環(huán)
          // 這是因為數(shù)組已排序，后邊元素更大，子集和一定超過 target
          if (target - choices[i] < 0) {
              break;
          }
          // 嘗試：做出選擇，更新 target, start
          state.push_back(choices[i]);
          // 進行下一輪選擇
          backtrack(state, target - choices[i], choices, i, res);
          // 回退：撤銷選擇，恢復到之前的狀態(tài)
          state.pop_back();
      }
  }
  
  /* 求解子集和 I */
  vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
      vector<int> state;              // 狀態(tài)（子集）
      sort(nums.begin(), nums.end()); // 對 nums 進行排序
      int start = 0;                  // 遍歷起始點
      vector<vector<int>> res;        // 結果列表（子集列表）
      backtrack(state, target, nums, start, res);
      return res;
  }

如圖 13-12 所示，為將數(shù)組 $[3,4,5]$ 和目標元素 $9$ 輸入到以上代碼后的整體回溯過程。

圖 13-12   子集和 I 回溯過程

考慮重復元素的情況

相比于上題，本題的輸入數(shù)組可能包含重復元素，這引入了新的問題。例如，給定數(shù)組 $[4,\hat{4},5]$ 和目標元素 $9$ ，則現(xiàn)有代碼的輸出結果為 $[4,5],[\hat{4},5]$ ，出現(xiàn)了重復子集。

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

圖 13-13   相等元素導致的重復子集

1.   相等元素剪枝

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

與此同時，本題規(guī)定中的每個數(shù)組元素只能被選擇一次。幸運的是，我們也可以利用變量 start 來滿足該約束：當做出選擇 $x_i$ 后，設定下一輪從索引 $i+1$ 開始向后遍歷。這樣即能去除重復子集，也能避免重復選擇元素。

2.   代碼實現(xiàn)

subset_sum_ii.cpp

/* 回溯算法：子集和 II */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // 子集和等于 target 時，記錄解
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // 遍歷所有選擇
    // 剪枝二：從 start 開始遍歷，避免生成重復子集
    // 剪枝三：從 start 開始遍歷，避免重復選擇同一元素
    for (int i = start; i < choices.size(); i++) {
        // 剪枝一：若子集和超過 target ，則直接結束循環(huán)
        // 這是因為數(shù)組已排序，后邊元素更大，子集和一定超過 target
        if (target - choices[i] < 0) {
            break;
        }
        // 剪枝四：如果該元素與左邊元素相等，說明該搜索分支重復，直接跳過
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // 嘗試：做出選擇，更新 target, start
        state.push_back(choices[i]);
        // 進行下一輪選擇
        backtrack(state, target - choices[i], choices, i + 1, res);
        // 回退：撤銷選擇，恢復到之前的狀態(tài)
        state.pop_back();
    }
}

/* 求解子集和 II */
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
    vector<int> state;              // 狀態(tài)（子集）
    sort(nums.begin(), nums.end()); // 對 nums 進行排序
    int start = 0;                  // 遍歷起始點
    vector<vector<int>> res;        // 結果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}

圖 13-14 展示了數(shù)組 $[4,4,5]$ 和目標元素 $9$ 的回溯過程，共包含四種剪枝操作。請你將圖示與代碼注釋相結合，理解整個搜索過程，以及每種剪枝操作是如何工作的。

圖 13-14   子集和 II 回溯過程