网站备案接入商是什么,app运营策略,唐山网站建设开发,wordpress xampp文章目录 90. 子集 II题目描述回溯算法 90. 子集 II
题目描述
给你一个整数数组 nums #xff0c;其中可能包含重复元素#xff0c;请你返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。返回的解集中#xff0c;子集可以按 任意顺序 … 文章目录 90. 子集 II题目描述回溯算法 90. 子集 II
题目描述
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例 1 输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2 输入nums [0] 输出[[],[0]] 提示
1 nums.length 10-10 nums[i] 10
回溯算法
class Solution {
public:// 主函数接受一个整数数组作为输入返回该数组所有可能的不重复子集vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end()); // 先对数组进行排序以便处理重复元素vectorbool used(nums.size(), false); // 记录每个元素是否被使用避免重复子集backstracking(nums, 0, used); // 开始回溯算法return result; // 返回所有找到的子集}private:vectorvectorint result; // 用于存储所有可能的子集vectorint path; // 用于存储当前路径即当前构造的子集// 回溯函数void backstracking(vectorint nums, int start, vectorbool used) {result.push_back(path); // 将当前路径添加到结果集// 遍历数组中的每个元素for (int i start; i nums.size(); i) {// 如果当前元素和前一个元素相同并且前一个元素没有被使用过// 则跳过当前元素避免产生重复的子集if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue;}path.push_back(nums[i]); // 将当前元素加入到路径used[i] true; // 标记当前元素为已使用backstracking(nums, i 1, used); // 递归调用继续向路径添加元素path.pop_back(); // 回溯移除路径中的当前元素used[i] false; // 取消当前元素的已使用标记}}
};这段代码实现了一个基于回溯算法的解决方案来生成所有可能的子集包括处理重复元素以避免重复子集的情况。首先它通过排序输入数组nums来处理可能的重复元素。used数组用来跟踪每个元素的使用情况确保在生成子集时不会因为重复元素而产生重复的子集。
在backstracking方法内部每次调用都会将当前path加入到结果集result中然后通过一个循环遍历nums数组的剩余部分。如果当前元素与前一个元素相同并且前一个元素没被使用过循环会跳过当前元素通过这种方式来避免生成重复的子集。
每次递归调用backstracking都会向path中添加一个新元素并且更新used数组来反映这个元素已经被使用过了。一旦完成了对当前元素的处理代码会通过path.pop_back()和used[i] false来回溯即移除当前元素并标记为未使用以便于下次循环可以使用该元素的下一个元素。
