414-回溯算法-挑数字问题(回溯高效)

忘是亡心i 2022-09-05 00:24 127阅读 0赞

## 题目如下 ##

**挑选数字：有一组整数，请挑选出一组数字，让他们的和等于指定的值，存在解打印，不存在打印**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

## 解决方法1（子集树+剪枝） ##

![在这里插入图片描述][255213033f9f4a24b8af3d1632087174.png]  
**r是未处理的元素的和，未处理的节点是节点已经访问处理过了，不管是选择了还是不选择，就是算处理过了**

int arr[] = {
         4,8,12,16,7,9,3 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    int number = 18;
    vector<int> x;//记录选择的数字
    int sum = 0;//记录所选择数字的和
    int r = 0;//记录未处理的数字的和
    void func(int i)
    {
        
    	if (i == length)//到达叶子节点
    	{
        
    		if (sum != number)
    		{
        
    			return;
    		}
    		for (int v : x)
    		{
        
    			cout << v << " ";
    		}
    		cout << endl;
    	}
    	else//深度遍历的过程中
    	{
        
    		r -= arr[i];//处理当前i节点
    		//r是未处理的元素的和，未处理的节点是节点已经访问处理过了，不管是选择了还是不选择，就是算处理过了
    		if (sum + arr[i] <= number)//剪左树枝  已选择的数字的和+即将要选择的数字
    		{
        
    			sum += arr[i];
    			x.push_back(arr[i]);
    			func(i + 1);
    			sum -= arr[i];
    			x.pop_back();
    		}
    
    		if (sum + r >= number)//剪右树枝  已选择的数字的和+剩余的可以被选择的数字的和(i+1,i+2....n)>=number才进入右孩子
    		{
        
    			func(i + 1);
    		}
    		r += arr[i];//回溯到父节点
    	}
    }
    int main()
    {
        
    	for (int v : arr)
    	{
        
    		r += v;
    	}
    	func(0);
    	return 0;
    }

![在这里插入图片描述][102e8ad2315f43918b9f0ed7996bc4fb.png]

## 解决方法2（更高效的回溯思想） ##

枚举法  
**先举个例子：**  
**我们在4, 5，6，7中挑选数字，和 满足：  
满足条件的number：18**

我们可以挑以4开头，也可以挑以5开头，也可以挑以6开头，也可以挑以7开头。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**形成了1棵四叉树。  
往左边走，深度遍历，如果先选择4，选了4以后，还能选什么呢？就是看4后边有3个元素（5,6，7），还可以选择5或者6或者7。然后选了5之后，还剩下6,7，然后选了6，还有7。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

**如果先选择5，就不选4了，因为选4的时候已经把5选过了。以此类推。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
一共有8个分枝到达叶子节点。（8个叶子节点）  
**如果用子集树就是2^4=16，用于处理目标不明确的。  
而此题目标是明确的，求选择的数字的和指定值。**

**我们拿着18遍历去减，判断。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**根节点往左走，选了4,18-4,14，然后选择5，14-5=9，然后选择6,9-6=3，然后底下的7大于3，所以这路找不出来，回退到父节点5，判断7，以此类推下去。**  
递归1次就是1叉树，递归2次就是而2叉树，递归3次就是3叉树…  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
4次for循环，形成四叉树  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**循环的意思是**：从当前元素开始一直遍历到后面的剩余的所有元素进行递归，递归几次就是几叉树，以此类推。number==0，代表找到一组序列了

int arr[] = {
         4,8,12,16,7,9,3,3 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    int number = 18;
    vector<int> vec;//存放选择的数字
    void func(int i, int number)
    {
        
    	if (number == 0)
    	{
        
    		for (int v : vec)
    		{
        
    			cout << v << " ";
    		}
    		cout << endl;
    	}
    	else
    	{
        
    		//以当前节点开始，把剩余元素的孩子节点生成
    		for (int k = i; k < length; ++k)
    		{
        
    			if (number >= arr[k])//arr[K]值小于number（待组成的元素值），才可以选择arr[k]，不然number减一下就变成负数了
    			{
        
    				vec.push_back(arr[k]);
    				//当前层遍历到下一层的时候   arr[k] != arr[k-1]
    				//如果不允许重复选择元素：
    				func(k + 1, number - arr[k]);
    				//k+1就是少一个元素，孩子节点少1个叉树
    				//number扣除当前选择的值
    				//遍历孩子节点，arr[k]的孩子节点
    				
    				//如果允许重复选择元素：
    				//func(k, number - arr[k]);
    				//孩子的叉树数和父亲的叉树数一样
    				//相当于当前元素可以重复选择
    				
    				vec.pop_back();//回溯到父节点
    			}
    		}
    	}
    }
    int main()
    {
        
    	func(0, number);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/d9224b4348564c0895437f2e58b03fba.png
[255213033f9f4a24b8af3d1632087174.png]: /images/20220829/76e5daac7a114b3fb8d091f16d8b8abe.png
[102e8ad2315f43918b9f0ed7996bc4fb.png]: /images/20220829/ae391280ff9748918d5c8216633ba16b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/07722c3bf1714e78b95c02b7d2644ff2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/2c7a7c63555c422fb49086922ed20a70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/2b4c71b2a09a4516829cf027ba6fc1dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/677ab3dd98de45a3a4bd17039513d9c3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a7ba936ce9854685bd96034149cc04ca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/fe9b66efa349497183b087638e1eabf6.png