【数据结构】回溯，递归，归并算法及使用场景

ゝ一世哀愁。 2022-05-16 13:04 154阅读 0赞

## 一、求子集a ##

**1、题目**  
已知一组数（其中**无重复元素**），求这组数可以组成的所有子集；  
结果中不可有重复的子集  
例如：  
nums\[\] =\[1,2,3\]  
结果为：【\[\], \[1\] , \[1,2\], \[1,2,3\], \[1,3\], \[2\] ,\[2,3\], \[3\] 】

解题思路：  
利用栈（vector）来递归实现；  
**2、程序实现**

#include<iostream>
    #include<vector>
    using namespace std;
    
    class solution
    {
    public:
    	std::vector<std::vector<int>>  subsets(std::vector<int>& nums)
    	{
    		std::vector<std::vector<int>>  result;
    		std::vector<int> item;
    		result.push_back(item);
    		generate(0, nums, item,result);
    		
    		return result;
    	}
    	private:
    		void generate(int i , 
    			          std::vector<int>&nums, 
    			           std::vector<int>&item,
    			            std::vector<std::vector<int>>&result)
    		{
    			if(i >=  nums.size())
    			{
    				return ;
    			}
    			item.push_back(nums[i]);
    			result.push_back(item);
    
    			generate( i+1, nums, item, result);
    
    			item.pop_back();
    			generate( i+1 ,nums, item,result);
    		}
    };
    
    int main()
    {
    	std::vector<int> nums;
    	nums.push_back(1);
    	nums.push_back(2);
    	nums.push_back(3);
    
    	std::vector<std::vector<int>> result;
    
    	solution solve;
    	result = solve.subsets(nums);
    
    	for(int i = 0; i < result.size(); i++)
    	{
    		if(result[i].size() == 0)
    		{
    			printf("[]");
    		}
    		for(int j = 0; j<result[i].size(); j++)
    		{
    			printf("[%d]",result[i][j]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

**3、结果展示**  
![70][]

## 二、求子集b ##

**1、题目**  
已知一组数（其中**有重复元素**），求这组数可以组成的所有子集，结果中无重复的子集。  
如：nums\[\] = \[2,1,2,2\]  
结果为：【\[\] , \[1\] , \[1,2\],\[1,2,2\], \[1,2,2,2\], \[2\],\[2,2\],\[2,2,2\]】

解题思路：有两种重复原因：  
（1）不同位置的元素组成的集合是同一个子集，顺序相同  
（2）不同位置的元素组成的集合是同一子集，顺序不同。（集合是无序的）  
将原数组排序，再使用set去查看；  
\[2,1,2,2\]排序后\[1,2,2,2\],无论如何，都只会出现\[1,2,2\]的情况  
**2、程序实现**

#include<iostream>
    #include<vector>
    #include<set>
    #include<algorithm>
    using namespace std;
    
    class solution
    {
    public:std::vector<std::vector<int>> subsetWithDup(std::vector<int>& nums)
    	   {
    		   std::vector<int> item;
    		   std::vector<std::vector<int>> result;
    		   std::set<std::vector<int>> res_set;
    
    		   std::sort(nums.begin(),nums.end());
    		   result.push_back(item);
    
    		   generate(0, nums, result, item, res_set);
    		   return result;
    	   }
    private:
    	void generate(int i ,
    		      std::vector<int>&nums, 
    			  std::vector<std::vector<int>> &result,
    			  std::vector<int> &item,
    			  std::set<std::vector<int>>& res_set)
    	{
    		if(i >= nums.size())
    		{
    			return ;
    		}
    
    		item.push_back(nums[i]);
    		if(res_set.find(item) == res_set.end())//在set中没找到item，则插入
    		{
    			result.push_back(item);
    			res_set.insert(item);
    
    		}
    
    		generate(i+1 , nums,  result, item, res_set);
    		item.pop_back();
    		generate(i+1 ,  nums,  result, item ,res_set);
    	}
    };
    
    int main()
    {
    	std::vector<int> nums;
    	nums.push_back(2);
    	nums.push_back(1);
    	nums.push_back(2);
    	nums.push_back(2);
    
    	std::vector<std::vector<int>>  result;
    
    	solution solve;
    	result = solve.subsetWithDup(nums);
    
    	for(int  i = 0;i < result.size();i++ )
    	{
    		if(result[i].size() == 0)
    			printf("[]");
    
    		for(int  j = 0;j < result[i].size();j++)
    		{
    			printf("[%d]", result[i][j]);
    		}
    		printf("\n");
    
    	}
    	return 0;
    }

**3、结果展示**  
![70 1][]

## 三、组合数之和\#\# ##

**1、题目**  
已知一数组（其中有相同元素），求这组数可以组成的所有子集中，  
子集中的各个元素和为整数target的子集，结果中无重复子集  
如：nums\[\] = \[10,1,2,7,6,1,5\], target = 8;  
结果为：【\[1,7\],\[1,2,5\] , \[2,6\] ,\[1,1,6\]】

解题思路：  
利用剪枝操作；在搜索回溯过程中进行剪枝操作，递归调用时，计算已选择元素的和sum；  
若sum>target,就不再进行更深的搜索，直接返回。  
**2、程序实现**

#include<iostream>
    #include<vector>
    #include<set>
    #include<algorithm>
    using namespace std;
    
    class solution
    {
    public:
    	std::vector<std::vector<int>> combinationsum(std::vector<int>& nums,int target)
    	{
    		std::vector<std::vector<int>> result;
    		std::vector<int> item;
    		std::set<std::vector<int>>  res_set;
    
    		std::sort(nums.begin(),nums.end());
    
    		generate( 0 , nums, result, item , res_set, 0 , target);
    		return result;
    
    	}
    
    private:
    	void generate(int i , 
    		           std::vector<int>&nums,
    				   std::vector<std::vector<int>>& result,
    				   std::vector<int>& item,
    				   std::set<std::vector<int>>res_set,
    				   int sum,
    				   int target
    				   )
    
    	{
    		if(sum > target || i >= nums.size())
    		{
    			return ;
    		}
    
    		sum += nums[i];
    		item.push_back(nums[i]);
    
    		if(sum == target &&res_set.find(item) == res_set.end())
    		{
    			result.push_back(item);
    			res_set.insert(item);
    		}
    
    		generate(i+1,  nums,  result,  item,  res_set,  sum,  target);
    		sum = sum - nums[i];//**************************
    		item.pop_back();
    		generate(i+1,  nums,  result,  item,  res_set,  sum,  target);
    
    	}
    
    };
    
    
    int main()
    {
    	std::vector<int> nums;
    	nums.push_back(10);
    	nums.push_back(1);
    	nums.push_back(2);
    	nums.push_back(7);
    	nums.push_back(6);
    	nums.push_back(1);
    	nums.push_back(5);
    
    	std::vector<std::vector<int>> result;
    	solution solve;
    
    	result = solve.combinationsum(nums,8);
    	
    	for(int  i = 0;i < result.size();i++ )
    	{
    		if(result[i].size() == 0)
    			printf("[]");
    
    		for(int  j = 0;j < result[i].size();j++)
    		{
    			printf("[%d]", result[i][j]);
    		}
    		printf("\n");
    
    	}
    
    	return 0;
    }

**3、结果展示**  
![70 2][]

## 四、生成括号 ##

**1、题目**  
已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能;  
解题思路：  
n组括号，有2^2n种可能  
例如：有一组括号：“（（”，“））”，“（）”，“）（”  
**2、程序实现**

#include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    
    class solution
    {
    public:
    	std::vector<std::string> generateParenthesis(int n)
    	{
    		std::vector<std::string> result;
    		generate("",n,n,result);
    		return result;
    	}
    
    private:
    	void generate(std::string item , int left,int right,std::vector<std::string>&result)
    	{
    		if(left == 0 && right == 0)
    		{
    			result.push_back(item);
    			return ;
    		}
    
    		if(left > 0)
    		{
    			generate(item + '(', left-1, right, result);
    		}
    
    		if(left<right)
    		{
    			generate(item +  ')',left,right-1,result);
    		}
    	}
    
    };
    
    int main()
    {
    	solution solve;
    	std::vector<std::string > result;
    	result = solve.generateParenthesis(4);
    	for(int  i = 0;i <result.size(); i++)
    	{
    		printf("%s\n",result[i].c_str());
    	}
    	return 0;
    }

**3、结果展示**  
![70 3][]

## 五、归并排序 ##

**1、题目**  
已知两个已排序的数组，将这两个已排序的数组合并为一个排序数组  
解题思路：  
在两个数组中，分别设置一个指针，指向数组的首元素，将两个指针对应的元素相比较，符合条件的存放在总数组中，循环上述步骤即可  
**2、程序实现**

#include<iostream>
    #include<vector>
    using namespace std;
    class solution
    {
    public:
    	void Merge_two_vec(std::vector<int>& vec1, 
    		               std::vector<int>& vec2,
    					   std::vector<int>& vec)
    {
    		int  i = 0;
    		int  j = 0;
    		while(i<vec1.size() && j<vec2.size())
    		{
    			if(vec1[i] < vec2[j])
    			{
    				vec.push_back(vec1[i]);
    				i++;
    			}
    			else
    			{
    				vec.push_back(vec2[j]);
    				j++;
    			}
    		}
    
    		for(; i<vec1.size();i++)
    		{
    			vec.push_back(vec1[i]);
    		}
    		for(;j<vec2.size();j++)
    		{
    			vec.push_back(vec2[j]);
    		}
    	}
    };
    
    
    int main()
    {
    	int test[] = {1,3,5,7,9};
    	int test2[] = {2,4,6,8,10,13,15};
    	std::vector<int> vec1;
    	std::vector<int> vec2;
    	std::vector<int> vec;
    
    	for(int i = 0;i<5;i++)
    	{
    		vec1.push_back(test[i]);
    	}
    
    	for(int i = 0;i< 7 ; i++)
    	{
    		vec2.push_back(test2[i]);
    	}
    	solution solve;
    
    	solve.Merge_two_vec(vec1, vec2,vec);
    
    	for(int i = 0;i<vec.size();i++)
    	{
    		printf("[%d]",vec[i]);
    	}
    	printf("\n");
    
    	return 0;
    }

**3、结果展示**  
![70 4][]

[70]: /images/20220516/b83eeeb3a6ba442ca8e798ac99c9f4cd.png
[70 1]: /images/20220516/2f1a9086e08d4f34bcfda7baa96fc9c4.png
[70 2]: /images/20220516/de1a514b561743e29d50f3ecfb1ab1b6.png
[70 3]: /images/20220516/4a761c6e697240a8a051b1c2dc5d49ea.png
[70 4]: /images/20220516/4818ff2d27be4ced8a36ca4d5750b50b.png