回溯法的理解
本文参考了一位大佬的题解，详细的介绍了回溯法：链接
上一篇刷题文： 回溯法经典问题之组合
记住住一句话：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: vector<int> path; vector<vector<int>> result; void backtrack(vector<int>& nums,int index) { result.push_back(path); if(index==nums.size()) { return; } for(int i=index;i<nums.size();i++) { path.push_back(nums[i]); backtrack(nums,i+1); path.pop_back(); } } public: vector<vector<int>> subsets(vector<int>& 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: vector<int> path; vector<vector<int>> result; void backtrack(vector<int>& nums,int index,vector<bool>& used) { result.push_back(path); if(index==nums.size()) { return; } for(int i=index;i<nums.size();i++) { if(i>0&&nums[i-1]==nums[i]&&used[i-1]==0) continue; path.push_back(nums[i]); used[i]=1; backtrack(nums,i+1,used); used[i]=0; path.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { path.clear(); result.clear(); vector<bool> used; used.resize(nums.size()); sort(nums.begin(),nums.end()); backtrack(nums,0,used); return result; } };
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
