哪家网站开发好,常熟有做网站的网络公司吗,wordpress 获取总页数,母婴护理服务网站模板第五章 子集题目理解步骤树形结构递归函数递归结束的条件单层逻辑 代码 子集II题目理解步骤树形结构递归函数递归结束的条件单层逻辑 代码 子集
力扣链接
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。… 第五章 子集题目理解步骤树形结构递归函数递归结束的条件单层逻辑 代码 子集II题目理解步骤树形结构递归函数递归结束的条件单层逻辑 代码 子集
力扣链接
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2 输入nums [0] 输出[[],[0]] 提示 1 nums.length 10 -10 nums[i] 10 nums 中的所有元素 互不相同
题目理解
一看就是 回溯组合 , 那么跟 回溯组合有什么不同呢? 回溯组合中的, 接收结果是在叶子节点, 而这个子集是收集各个节点上的数据
步骤
树形结构 递归函数
首先, 还是两个全局变量, 一个记录单层结果, 一个记录全部结果
vectorint path; // 记录单层结果
vectorvectorint result; // 记录全部结果函数返回的类型是 void, 组合 — — startindex
void backtracking(vectorint nums, int startindex)递归结束的条件
由于是要收集每个节点上的数据, 所以我们就可以不用写条件, 直接收录
result.push_back(path);单层逻辑
单层逻辑 和 回溯组合中的 单层逻辑是一样的
for(int i startindex; i nums.size(); i)
{path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();
}代码
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums, int startindex){result.push_back(path);for(int i startindex; i nums.size(); i){path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {backtracking(nums, 0);return result;}
};子集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
题目理解
哈哈, 跟上面的子集大体上是一样的, 唯一不同的是 有重复的元素 解集不能包含重复的子集 那么下一步的操作肯定就是 去重
步骤
树形结构 从上面的树形图可以看出:
同一树层上的 2 要去重 — — 树层去重同一树枝上的 2 不能去重 — — 树枝不去重 树层去重, 树枝不去重的原因: 树层去重 — — 因为已经排序, 那么第一个 2 具有的组合 包含了后面的 2 具有的组合 树枝不去重 — — 因为 [1, 2 ] 和 [1, 2, 2] 是两个不同的结果, 一个是第一个 2, 一个是第二个 2
递归函数
首先, 还是两个全局变量, 一个记录单层结果, 一个记录全部结果
vectorint path; // 记录单层结果
vectorvectorint result; // 记录全部结果函数返回的类型是 void 组合 — — startindex 去重 — — used数组
void backtracking(vectorint nums, vectorbool used, int startindex)递归结束的条件
由于是要收集每个节点上的数据, 所以我们就可以不用写条件, 直接收录
result.push_back(path);单层逻辑
子集 去重 for(int i startindex; i nums.size(); i){// 树层去重, 树枝不去重的关键if(i 0 ( nums[i] nums[i - 1] ) (used[i - 1] false)){continue;}path.push_back(nums[i]);used[i] true;backtracking(nums, used, i 1);path.pop_back();used[i] false;}代码
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums, vectorbool used, int startindex){// 子集是搜集每一个节点, 不需要结束条件result.push_back(path);for(int i startindex; i nums.size(); i){// 树层去重, 树枝不去重的关键if(i 0 ( nums[i] nums[i - 1] ) (used[i - 1] false)){continue;}path.push_back(nums[i]);used[i] true;backtracking(nums, used, i 1);path.pop_back();used[i] false;}}vectorvectorint subsetsWithDup(vectorint nums) {vectorbool used(nums.size(), false);sort(nums.begin(), nums.end()); // 排序很重要backtracking(nums, used, 0);return result;}
};要人家服只能说服不能压服压服的结果总是压而不服以力服人是不行的 — — 毛泽东
