C++回溯算法中子集问题如何解决

其他教程   发布日期:2023年08月30日   浏览次数:453

这篇文章主要介绍了C++回溯算法中子集问题如何解决的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++回溯算法中子集问题如何解决文章都会有所收获,下面我们一起来看看吧。

一、子集

子集问题与其它问题最大的不同就是:每次递归,不止考虑叶子节点,而是考虑所有节点!

体现在代码上,就是每次递归都先result.push_back(path);

  1. class Solution {
  2. private:
  3. vector<int> path;
  4. vector<vector<int>> result;
  5. void backtracking(vector<int>& nums,int index){
  6. result.push_back(path);
  7. if(index>=nums.size())
  8. return;
  9. for(int i=index;i<nums.size();i++){
  10. path.push_back(nums[i]);
  11. backtracking(nums,i+1);
  12. path.pop_back();
  13. }
  14. }
  15. public:
  16. vector<vector<int>> subsets(vector<int>& nums) {
  17. backtracking(nums,0);
  18. return result;
  19. }
  20. };

二、子集II

本题与上题唯一的区别在于:输入样例有重复数字,但又要求结果不能重复

本题与组合总和II是一个套路,即:横向遍历不可重复,纵向遍历可重复

体现在代码上,就是if(i>index&&nums[i]==nums[i-1]) continue;

  1. class Solution {
  2. private:
  3. vector<int> path;
  4. vector<vector<int>> result;
  5. void backtracking(vector<int>& nums,int index){
  6. result.push_back(path);
  7. if(index>=nums.size()) return;
  8. for(int i=index;i<nums.size();i++){
  9. if(i>index&&nums[i]==nums[i-1])
  10. continue;
  11. path.push_back(nums[i]);
  12. backtracking(nums,i+1);
  13. path.pop_back();
  14. }
  15. }
  16. public:
  17. vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  18. sort(nums.begin(),nums.end());
  19. backtracking(nums,0);
  20. return result;
  21. }
  22. };

三、递增子序列

这题严格来说并不是子集问题,但是有一点希望和子集II对比一下,就是同一层元素不能重复的问题,这一题因为元素不能排序,所以在判断元素是否重复的问题上,并不能采用类似于上一题的if(i>index&&nums[i]==nums[i-1]) continue;方法,而是应该开辟一个used数组记录每一层元素是否已出现过,其实上一题也能用这种方法,不过上一题没这个必要

还要注意used数组开辟的位置是在backtracking函数内部,意思很明显:used数组只管记录本层元素,至于下一层元素,则要开辟新的ued数组来记录

  1. class Solution {
  2. private:
  3. vector<int> path;
  4. vector<vector<int>> result;
  5. void backtracking(vector<int>& nums,int index){
  6. if(path.size()>1){
  7. result.push_back(path);
  8. if(index==nums.size()) return;
  9. }
  10. int used[201]={0};//记录本层元素是否重复使用,新的一层都会重新定义
  11. for(int i=index;i<nums.size();i++){
  12. if(used[nums[i]+100]==1||(!path.empty()&&nums[i]<path.back()))
  13. continue;
  14. used[nums[i]+100]=1;
  15. path.push_back(nums[i]);
  16. backtracking(nums,i+1);
  17. path.pop_back();
  18. }
  19. }
  20. public:
  21. vector<vector<int>> findSubsequences(vector<int>& nums) {
  22. backtracking(nums,0);
  23. return result;
  24. }
  25. };

以上就是C++回溯算法中子集问题如何解决的详细内容,更多关于C++回溯算法中子集问题如何解决的资料请关注九品源码其它相关文章!