C++算法练习-day61——90.子集2

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求找出给定数组的所有子集（幂集），但数组可能包含重复元素，要求结果中的子集是唯一的（不包含重复的子集）。为了解决这个问题，我们可以先对数组进行排序，然后在回溯过程中跳过重复的元素，以确保生成的每个子集都是唯一的。

代码:

#include <vector>  
#include <algorithm> // 包含sort函数  
  
class Solution {  
public:  
    // 回溯函数，用于生成所有唯一的子集  
    void Backstracking(vector<vector<int>>& ans, vector<int>& pos, vector<int>& nums, int index) {  
        // 当遍历到数组的末尾或已经遍历完所有可能的元素时，将当前构建的子集加入结果集中  
        if (index == nums.size()) {  
            ans.push_back(pos); // 将当前子集pos加入结果集ans  
            return; // 返回上一层继续构建其他子集（但实际上这里不会返回，因为函数会在循环结束后自然结束）  
        }  
          
        // 遍历当前index之后的所有元素（由于数组已排序，可以利用这个性质跳过重复元素）  
        for (int i = index; i < nums.size(); ++i) {  
            // 如果当前元素与前一个元素相同（且不是第一个元素，因为第一个元素总是可以加入的），则跳过当前元素  
            // 这是为了确保生成的每个子集都是唯一的  
            if (i > index && nums[i] == nums[i - 1]) {  
                continue;  
            }  
              
            pos.push_back(nums[i]); // 将nums[i]加入当前子集pos  
            Backstracking(ans, pos, nums, i + 1); // 递归调用，尝试加入下一个元素  
            pos.pop_back(); // 回溯，撤销选择，尝试其他可能的子集  
        }  
    }  
  
    // 主函数，用于调用回溯函数并返回所有唯一的子集  
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {  
        vector<vector<int>> ans; // 存储所有子集的结果集  
        vector<int> pos; // 当前正在构建的子集  
        sort(nums.begin(), nums.end()); // 对数组进行排序，以便在回溯过程中跳过重复元素  
        Backstracking(ans, pos, nums, 0); // 从第一个元素开始构建子集  
        return ans; // 返回所有唯一的子集  
    }  
};

知识点摘要

1. 回溯算法：通过递归尝试构建解的一部分，并在每一步决定是否继续构建或撤销当前选择，以探索所有可能的解。
2. 递归：函数调用自身的方法，常用于解决可以分解为相似子问题的问题。
3. 向量（Vector）：C++ STL中的动态数组，可以动态增长和缩小。
4. 排序：对数组进行排序，以便在回溯过程中利用排序后的性质（如跳过重复元素）。
5. 条件判断：在回溯算法中，条件判断用于确定何时停止递归（即找到了一个解）和何时回溯（即撤销当前选择，尝试其他可能的解）。

通过回溯算法和排序的结合，我们可以有效地生成给定数组的所有唯一子集。在回溯过程中，我们利用排序后的数组性质，跳过重复的元素，以确保生成的每个子集都是唯一的。这种方法不仅适用于包含重复元素的子集问题，还可以扩展到其他需要生成唯一组合或排列的问题。通过理解回溯算法的基本原理和排序的应用，我们可以解决许多看似复杂的问题，并生成所需的所有唯一解。