LeetCode78. 子集
https://leetcode-cn.com/problems/subsets/
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
思路
回溯模板:
void backtracking(选择列表,路径,结果)
{
if (终止条件)
{
存放结果;
return;
}
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表,路径,结果);
回溯,撤销处理结果
}
}
所有用回溯解决的问题都可以抽象为树形结构:
子集问题也是一种组合问题。如果说组合问题是收集树的叶子节点,那么子集问题是找树的所有节点。
回溯三部曲:
1.递归函数的返回值和参数
定义两个全局变量,一个用来存放符合条件的路径path,一个用来存放所有符合条件的路径的结果集合result。
函数里一定有一个参数:选择列表(数组nums)。
还有一个int型参数startIndex,这个参数用来记录本层递归中,选择列表从哪里开始遍历(选择列表就是数组nums)。随着递归控制树的纵向遍历,可选择的范围进而收缩,调整可选择的范围,就是要靠startIndex。
vector<vector<int>> result; //存放所有符合条件的路径的结果集合
vector<int> path; //存放符合条件的路径
void backtrack(vector<int>& nums, int startIndex)
2.递归函数的终止条件
当startIndex大于等于数组的长度时,已经没有元素可取了(即剩余选择列表为空),此时终止本层递归返回。
if (startIndex >= sz)
{
return;
}
3.搜索过程
我们定义的backtrack函数其实就像一个指针,在树中游走同时正确维护每个节点的属性。
//控制树的横向遍历
for (int i = startIndex; i < sz; ++i)
{
path.push_back(nums[i]);
backtrack(nums, i + 1); //递归:控制树的纵向遍历
path.pop_back();
}
代码
class Solution
{
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合
vector<int> path; //存放符合条件的路径
void backtrack(vector<int>& nums, int startIndex)
{
int sz = nums.size();
result.push_back(path);
if (startIndex >= sz)
{
return;
}
//控制树的横向遍历
for (int i = startIndex; i < sz; ++i)
{
path.push_back(nums[i]);
backtrack(nums, i + 1); //递归:控制树的纵向遍历
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums)
{
backtrack(nums, 0);
return result;
}
};
LeetCode90. 子集II
https://leetcode-cn.com/problems/subsets-ii/
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
思路
本题与LeetCode78. 子集有一个区别:
- 本题数组nums的元素是有重复的,但不能有重复的组合。
所以本题的大体思路与LeetCode78. 子集是相同的,重点是要去重。所谓去重,其实就是使用过的元素不能重复选取。
用回溯解决的问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过。
根据题意:元素在同一个组合内是可以重复的,但两个组合不能相同。同一树层上的是两个组合里的元素,所以我们要去重的是同一树层上的“使用过”;而同一树枝上的都是一个组合里的元素,所以不用去重。
要在代码层面实现以上的去重逻辑,就需要先对数组进行排序,然后定义一个bool类型数组used。这个数组的元素初始值都为false表示对应的candidate的元素都没被访问过。如果nums[i] == nums[i - 1]
并且 used[i - 1] == false
,就说明:前一个树枝,使用了nums[i - 1],也就是说同一树层使用过nums[i - 1],此时for循环里应该做continue的操作。
所有用回溯解决的问题都可以抽象为树形结构:
代码
class Solution {
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合
vector<int> path; //存放符合条件的路径
void backtrack(vector<int>& nums, vector<bool>& used, int startIndex)
{
int sz = nums.size();
result.push_back(path);
if (startIndex >= sz)
{
return;
}
//控制树的横向遍历
for (int i = startIndex; i < sz; ++i)
{
if (i >= 1 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, used, i + 1); //递归:控制树的纵向遍历
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
sort(nums.begin(), nums.end());
//used数组存放bool类型的元素,初始值都为false表示数组nums的元素都没被访问过
vector<bool> used(nums.size(), false);
backtrack(nums, used, 0);
return result;
}
};
LeetCode491. 递增子序列
https://leetcode-cn.com/problems/increasing-subsequences/
给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是 2 。
输入:[4, 6, 7, 7]
输出:[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
提示:
- 给定数组的长度不会超过15。
- 数组中的整数范围是 [-100,100]。
- 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况
思路
本题求递增子序列比较像是取有序的子集,而且本题也要求不能有相同的递增子序列。容易联想到LeetCode90. 子集II。
但是本题的去重逻辑与LeetCode90. 子集II不同。在LeetCode90. 子集II中我们是通过排序,再加一个标记数组来达到去重的目的;而本题求递增子序列,是不能对原数组进行排序的,排完序的数组就都是递增子序列了。
**所以不能使用之前的去重逻辑!那应该怎么进行去重呢?我们可以使用关联容器unordered_set
**记录本层元素是否重复使用,具体思路见代码和注释。
所有用回溯解决的问题都可以抽象为树形结构:
代码
class Solution {
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合
vector<int> path; //存放符合条件的路径
void backtrack(vector<int>& nums, int startIndex)
{
int sz = nums.size();
if (path.size() >= 2)
{
result.push_back(path);
}
if (startIndex >= sz)
{
return;
}
//使用unordered_set来对本层元素进行去重
unordered_set<int> uset;
//控制树的横向遍历
for (int i = startIndex; i < sz; ++i)
{
if ((path.size() >= 1 && nums[i] < path.back()) || uset.count(nums[i]))
{
continue;
}
// 记录这个元素在本层用过了,本层后面不能再用了
uset.insert(nums[i]);
path.push_back(nums[i]);
backtrack(nums, i + 1); //递归:控制树的纵向遍历
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums)
{
backtrack(nums, 0);
return result;
}
};