市场营销策划公司,优化网站入口页面的四个维度,做网站v1认证需要付费吗,宜春建设局网站食用指南#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识#xff1a;回溯法经典问题之组合 ♈️今日夜电波#xff1a;想着你—郭顶 1:09 ━━━━━━️#x1f49f;──────── 4:15 … 食用指南本文为作者刷题中认为有必要记录的题目 前置知识回溯法经典问题之组合 ♈️今日夜电波想着你—郭顶 1:09 ━━━━━━️──────── 4:15 ◀️ ⏸ ▶️ ☰ 关注点赞收藏您的每一次鼓励都是对我莫大的支持 目录
回溯法的理解 一、子集 二、子集II 回溯法的理解 本文参考了一位大佬的题解详细的介绍了回溯法链接
上一篇刷题文 回溯法经典问题之组合 记住一句话for循环横向遍历递归纵向遍历回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。 一、子集
题目链接78. 子集
题目描述 给你一个整数数组 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] 10nums 中的所有元素 互不相同 本题思路 采用经典的“回溯三部曲” 1、定义两个全局变量一个用来存放符合条件单一结果path一个用来存放符合条件结果的集合result。注意要记得用一个变量来记录遍历的位置。 2、回溯的主体回溯终止条件。path保存一组数据每次遍历到叶子节点再插入到result中并且回溯到上一个节点。 3、单层搜索的过程。for循环用来横向遍历递归的过程是纵向遍历。 特别注意 本题虽然同之前的组合问题差不多但是还是需要做一定的变化的依据题意我们都知道任何一个子集都是包涵空集的并且子集中一个元素也算子集。 于是根据题意写出以下题解
class Solution {
private:
vectorint path;
vectorvectorint result;void backtrack(vectorint nums,int index)
{result.push_back(path); if(indexnums.size()){return;}for(int iindex;inums.size();i){path.push_back(nums[i]);backtrack(nums,i1);path.pop_back();}}
public:vectorvectorint subsets(vectorint nums) {path.clear();result.clear();sort(nums.begin(),nums.end());backtrack(nums,0);return result;}
}; 二、子集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 本题思路 同样采用经典的“回溯三部曲”但是由于此题中的元素是可以重复的那这样必然会出现重复的子集因此我们需要进行剪枝操作。此时可以参考 回溯法经典问题之组合 中最后一题。我们也建立一个used用于标记是否使用过使用过元素。 特别注意 本题虽然同之前的题差不多但是还是需要做一定的变化的。比如插入的操作。 一图了解题解 ~以{1,2,2}为例 class Solution {
private:
vectorint path;
vectorvectorint result;
void backtrack(vectorint nums,int index,vectorbool used)
{result.push_back(path);if(indexnums.size()){return;}for(int iindex;inums.size();i){if(i0nums[i-1]nums[i]used[i-1]0)continue;path.push_back(nums[i]);used[i]1;backtrack(nums,i1,used);used[i]0;path.pop_back();}
}
public:vectorvectorint subsetsWithDup(vectorint nums) {path.clear();result.clear();vectorbool used;used.resize(nums.size());sort(nums.begin(),nums.end());backtrack(nums,0,used);return result;}
}; 感谢你耐心的看到这里ღ( ´ᴗ )比心如有哪里有错误请踢一脚作者o(╥﹏╥)o 给个三连再走嘛~
