回溯总结2（子集问题）
78 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路
回溯返回条件，index==num,size()
class Solution {
public:
vector<vector<int>>res;
void backtracing(vector<int>& nums,vector<int>& path,int startIndex){
if(startIndex==nums.size()){
return;
}
for(int i = startIndex;i<nums.size();i++){
path.push_back(nums[i]);
res.push_back(path);
startIndex++;
backtracing(nums,path,startIndex);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> path;
int startIndex=0;
res.push_back(path);
backtracing(nums,path,startIndex);
return res;
}
};
90 子集
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
参考组合总和||，关键是去重
有了index就不需要used数组
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums, int startIndex) {
// 每个路径都是一个合法的子集，直接加入结果
res.push_back(path);
// 遍历当前可选的数字
for(int i = startIndex; i < nums.size(); i++) {
// 跳过重复元素（同一层）
if(i > startIndex && nums[i] == nums[i-1]) {
continue;
}
// 选择当前数字
path.push_back(nums[i]);
// 递归搜索
dfs(nums, i + 1);
// 回溯，撤销选择
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序，便于去重
dfs(nums, 0);
return res;
}
};
491 递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]。
- 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
题目要求递增子序列大小至少为2
思路
- 剪枝，选出所有组合，然后找到递增序列
unordered_set<int> uset;是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！
注意：
// 用于判断是否可以将当前元素添加到路径中
bool isValid(vector& nums, int i, unordered_set& used) {
return (path.empty() || nums[i] >= path.back()) && !used.count(nums[i]);
}
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
// 用于判断是否可以将当前元素添加到路径中
bool isValid(vector<int>& nums, int i, unordered_set<int>& used) {
return (path.empty() || nums[i] >= path.back()) && !used.count(nums[i]);
}
void backtracing(vector<int>& nums, int startIndex) {
if (path.size() >= 2) { // 确保只存储有效长度的路径
res.push_back(path);
}
if (startIndex == nums.size()) return;
unordered_set<int> used; // 用于记录当前层级访问过的数字
for (int i = startIndex; i < nums.size(); i++) {
// 使用封装后的 isValid 函数来判断是否可以继续
if (!isValid(nums, i, used)) {
continue;
}
used.insert(nums[i]); // 记录当前数字
path.push_back(nums[i]);
backtracing(nums, i + 1);
path.pop_back(); // 回溯
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
res.clear();
path.clear();
backtracing(nums, 0);
return res;
}
};
1. 布尔数组标记法 (适用于子集问题)
特点：
- 实现简单，空间效率高。
- 适用于一般的子集/组合问题，特别是对于需要返回所有可能的子集的情况。
举例题目：
- LeetCode 90: Subsets II（子集 II）：给定一个可能包含重复元素的整数数组
nums，返回所有可能的子集（包含空集）。需要去重。
题目描述：
输入: nums = [1, 2, 2]
输出:
[
[],
[1],
[1,2],
[2],
[2,2]
]
2. 计数map法 (适用于元素重复次数较多的情况)
特点：
- 高效处理重复元素较多的情况。
- 需要额外空间来存储每个元素的计数。
举例题目：
- LeetCode 90: Subsets II（子集 II）和 LeetCode 40: Combination Sum II（组合总和 II）：对于包含重复元素的数组，避免重复组合。
题目描述：
输入: candidates = [10,1,2,7,6,5], target = 8
输出:
[
[1, 2, 5],
[1, 7],
[2, 6]
]
3. 选或不选法 (适用于有限制的组合问题)
特点：
- 思路清晰，适合处理有选择限制的组合问题。
- 在某些情况下可能实现较复杂。
举例题目：
- LeetCode 78: Subsets：给定一个不含重复元素的整数数组，返回其所有子集。
题目描述：
输入: nums = [1, 2, 3]
输出:
[
[],
[1],
[2],
[3],
[1,2],
[1,3],
[2,3],
[1,2,3]
]
- LeetCode 46: Permutations（排列）：给定一个没有重复数字的序列，返回其所有可能的排列。
题目描述：
输入: nums = [1, 2, 3]
输出:
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
4. 交换法 (排列专用)
特点：
- 不需要额外数组来记录路径，直接在原数组上进行操作。
- 适用于排列问题，尤其是要求去重的排列。
举例题目：
- LeetCode 47: Permutations II：给定一个可包含重复数字的序列，返回所有不重复的排列。
题目描述：
输入: nums = [1, 1, 2]
输出:
[
[1, 1, 2],
[1, 2, 1],
[2, 1, 1]
]
总结：
- 布尔数组标记法：适合标准的子集问题，简单且高效。
- 计数map法：适合处理重复元素较多的情况，使用额外的计数信息来避免重复。
- 选或不选法：适合限制条件较为复杂的组合问题，尤其是元素选择有上限时。
- 交换法：专门用于排列问题，避免重复排列，操作在原数组上进行。
每种方法适用的场景不同，选择时需要考虑问题的性质、元素是否重复以及对时间空间的要求。
原文地址：https://blog.csdn.net/weixin_51147313/article/details/145269624
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！