回溯算法详解：力扣78题“子集”解题思路与代码实现

回溯算法详解：力扣78题“子集”解题思路与代码实现

引用

CSDN

1.

https://blog.csdn.net/Talking999/article/details/137266872

力扣第78题“子集”是一道经典的回溯算法题目。本文将详细讲解该题的解法，帮助读者理解回溯算法在子集问题中的应用。

题目描述

给定一个整数数组 nums，返回其所有可能的子集（幂集）。解集不能包含重复的子集。

思路分析

子集问题与组合问题和分割问题有所不同。如果将这些问题抽象为树型结构，可以发现：

• 组合问题和分割问题需要收集树的叶子节点
• 子集问题需要收集树的所有节点

子集问题是一种特殊的组合问题，因为子集是无序的，即{1,2}和{2,1}被视为同一个子集。因此，在回溯算法中，需要从startIndex开始遍历，避免重复取元素。

以示例nums = [1,2,3]为例，将其抽象为树型结构如下：

从图中可以看出，遍历整棵树的所有节点即可得到所有子集。

回溯算法实现

递归函数参数

需要定义两个全局变量：

• result：用于存储所有子集
• path：用于存储当前子集的元素

递归函数还需要一个参数startIndex，表示当前遍历的起始位置。

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {

递归终止条件

当startIndex大于等于数组长度时，说明已经遍历完所有元素，可以终止递归。

if (startIndex >= nums.size()) {
    return;
}

单层搜索逻辑

在单层搜索中，需要从startIndex开始遍历数组，将当前元素加入path，然后递归调用backtracking函数，最后回溯撤销当前选择。

for (int i = startIndex; i < nums.size(); i++) {
    path.push_back(nums[i]);    // 子集收集元素
    backtracking(nums, i + 1);  // 注意从i+1开始，元素不重复取
    path.pop_back();            // 回溯
}

完整代码实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

关于空集的保存

在代码中，result.push_back(path);这行代码非常重要。即使在递归开始时path为空，也会将空集加入result中。因此，最终结果中会包含所有可能的子集，包括空集。

总结

通过对比组合问题和分割问题，可以更好地理解子集问题的特点。回溯算法在解决这类问题时，关键在于正确设置递归终止条件和单层搜索逻辑。希望本文能帮助读者掌握子集问题的解法。

本文原文来自CSDN