閱讀(1.5k) 書簽贊(0) 我要糾錯(cuò)

C++子集和問(wèn)題

2023-09-20 09:23 更新

無(wú)重復(fù)元素的情況

Question

給定一個(gè)正整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)正整數(shù) target ，請(qǐng)找出所有可能的組合，使得組合中的元素和等于 target 。給定數(shù)組無(wú)重復(fù)元素，每個(gè)元素可以被選取多次。請(qǐng)以列表形式返回這些組合，列表中不應(yīng)包含重復(fù)組合。

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

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

1. 參考全排列解法

類似于全排列問(wèn)題，我們可以把子集的生成過(guò)程想象成一系列選擇的結(jié)果，并在選擇過(guò)程中實(shí)時(shí)更新“元素和”，當(dāng)元素和等于 target 時(shí)，就將子集記錄至結(jié)果列表。

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

subset_sum_i_naive.cpp

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

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

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

這是因?yàn)樗阉鬟^(guò)程是區(qū)分選擇順序的，然而子集不區(qū)分選擇順序。如圖 13-10 所示，先選 $4$ 后選 $5$ 與先選 $5$ 后選 $4$ 是兩個(gè)不同的分支，但兩者對(duì)應(yīng)同一個(gè)子集。

子集搜索與越界剪枝

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

為了去除重復(fù)子集，一種直接的思路是對(duì)結(jié)果列表進(jìn)行去重。但這個(gè)方法效率很低，有兩方面原因。

當(dāng)數(shù)組元素較多，尤其是當(dāng) target 較大時(shí)，搜索過(guò)程會(huì)產(chǎn)生大量的重復(fù)子集。
比較子集（數(shù)組）的異同非常耗時(shí)，需要先排序數(shù)組，再比較數(shù)組中每個(gè)元素的異同。

2. 重復(fù)子集剪枝

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

當(dāng)?shù)谝惠喓偷诙喎謩e選擇 $3$ 和 $4$ 時(shí)，會(huì)生成包含這兩個(gè)元素的所有子集，記為 $[3, 4, \dots]$ 。
之后，當(dāng)?shù)谝惠嗊x擇 $4$ 時(shí)，則第二輪應(yīng)該跳過(guò) $3$ ，因?yàn)樵撨x擇產(chǎn)生的子集 $[4, 3, \dots]$ 和 1. 中生成的子集完全重復(fù)。

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

前兩輪選擇 $3$ 和 $5$ ，生成子集 $[3, 5, \dots]$ 。
前兩輪選擇 $4$ 和 $5$ ，生成子集 $[4, 5, \dots]$ 。
若第一輪選擇 $5$ ，則第二輪應(yīng)該跳過(guò) $3$ 和 $4$ ，因?yàn)樽蛹? $[5, 3, \dots]$ 和 $[5, 4, \dots]$ 與第 1. 和 2. 步中描述的子集完全重復(fù)。

不同選擇順序?qū)е碌闹貜?fù)子集

圖 13-11 不同選擇順序?qū)е碌闹貜?fù)子集

總結(jié)來(lái)看，給定輸入數(shù)組 $[x_{1}, x_{2}, \dots, x_{n}]$ ，設(shè)搜索過(guò)程中的選擇序列為 $[x_{i_{1}}, x_{i_{2}}, \dots, x_{i_{m}}]$ ，則該選擇序列需要滿足 $i_{1} \leq i_{2} \leq ? \leq i_{m}$ ，不滿足該條件的選擇序列都會(huì)造成重復(fù)，應(yīng)當(dāng)剪枝。

3. 代碼實(shí)現(xiàn)

為實(shí)現(xiàn)該剪枝，我們初始化變量 start ，用于指示遍歷起點(diǎn)。當(dāng)做出選擇 $x_{i}$ 后，設(shè)定下一輪從索引 $i$ 開始遍歷。這樣做就可以讓選擇序列滿足 $i_{1} \leq i_{2} \leq ? \leq i_{m}$ ，從而保證子集唯一。

除此之外，我們還對(duì)代碼進(jìn)行了以下兩項(xiàng)優(yōu)化。

在開啟搜索前，先將數(shù)組 nums 排序。在遍歷所有選擇時(shí)，當(dāng)子集和超過(guò) target 時(shí)直接結(jié)束循環(huán)，因?yàn)楹筮叺脑馗?，其子集和都一定?huì)超過(guò) target 。

省去元素和變量 total ，通過(guò)在 target 上執(zhí)行減法來(lái)統(tǒng)計(jì)元素和，當(dāng) target 等于

0

時(shí)記錄解。

subset_sum_i.cpp

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

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

子集和 I 回溯過(guò)程

圖 13-12 子集和 I 回溯過(guò)程

考慮重復(fù)元素的情況

Question

給定一個(gè)正整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)正整數(shù) target ，請(qǐng)找出所有可能的組合，使得組合中的元素和等于 target 。給定數(shù)組可能包含重復(fù)元素，每個(gè)元素只可被選擇一次。請(qǐng)以列表形式返回這些組合，列表中不應(yīng)包含重復(fù)組合。

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

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

相等元素導(dǎo)致的重復(fù)子集

圖 13-13 相等元素導(dǎo)致的重復(fù)子集

1. 相等元素剪枝

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

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

2. 代碼實(shí)現(xiàn)

subset_sum_ii.cpp

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

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

子集和 II 回溯過(guò)程

圖 13-14 子集和 II 回溯過(guò)程

以上內(nèi)容是否對(duì)您有幫助：

在文檔使用的過(guò)程中是否遇到以下問(wèn)題：

內(nèi)容錯(cuò)誤
更新不及時(shí)
鏈接錯(cuò)誤
缺少代碼/圖片示列
太簡(jiǎn)單/步驟待完善
其他

更多建議：

提交建議

← C++全排列問(wèn)題

C++N皇后問(wèn)題 →

寫筆記

我要補(bǔ)充

查看完整版筆記