411-回溯算法思想

女爷i 2022-09-05 00:10 233阅读 0赞

## 回溯算法思想 ##

**回溯算法具有解题的通用性，但是效率有待提高**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**解空间的树是逻辑上的树。不是真实存在的数据结构。**

## 题目1 ##

**打印多少次123？**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**运行结果是：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**为什么会打印出8次123？**  
这个数组有3个元素，下标分别是0,1，2，  
**我们看下图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**我们把i的值可以理解成是数组的下标。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**我们之前学的二叉树的前序遍历，中序遍历，后序遍历，都是自己调自己2次**。只是当时它是调用，是二叉树的，所以起始条件是根节点。其实就像代码中的i=0一样，逐渐从根节点往叶子节点遍历，当指针到达叶子节点的时候，叶子节点遍历完了，递归就结束了。  
**i=0相当于在逻辑上是一个根节点，i+1相当于下一层，以此类推。相当于在二叉树中，由父节点走向孩子节点。当i=length的时候，相当于从根节点沿着某一个路径遍历到叶子节点上。**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6][]  
**当i=0的时候，我们看作二叉树的根节点**，0不等于3，就执行A这一句了，i=1,1不等于3，又进来执行A了，i=2，2不等于3，又进来执行A了，i=3。相当于深度遍历。3等于3了，达到if的条件了，递归结束了，打印1，2,3，然后不进入else语句了，然后这个函数执行完了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]  
**递归完还要一个一个回溯**  
回溯到i=2的节点上。这个节点刚才只是执行了A这一句，**现在要执行B这一句**，**i=3了**！达到if条件，打印1,2，3，然后不进入else语句了，然后这个函数执行完了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]  
递归结束，回溯到上面那个节点，它把A,B这两句都执行完了，当前这个函数执行完了，然后就回溯到A:func i=1这个节点上，执行B这一句的调用，i=2，2不等于3，然后递归，又执行A这一句，i=3，打印1,2，3，然后又回溯到父节点，执行B这一句，i=3，再次打印1,2，3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]  
**以此类推下去。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 10]  
**所以，最后打印8次1,2，3。**

## 问题2（打印原始序列的子集） ##

**我们现在想打印的是原始序列123的所有的子集**  
![在这里插入图片描述][7e403f98173842008f12af598ff9d656.png]  
**我们看下图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 11]  
**我们记录根节点往左走，记录为1，根节点往右走，记录为0**  
也就是说，往左走是执行A这句，往右走是执行B这句。  
**我们在最后打印的时候，得判断，把往左走的节点打印出来，把往右走的节点不打印出来。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 12]  
**这样就可以把子集打印出来了！**  
![在这里插入图片描述][8e5c5ac88c4a49d891e091d111e1d578.png]  
**即叶子节点的个数：2^n个**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**同一层的节点代表同一个下标，同一个下标对应的是数组的同一个元素**  
**往左走表示选择当前这个元素，往右走表示不选择当前这个元素**

/*
    子集树代码
    */
    void func(int arr[], int i, int length, int x[])
    {
        
    	if (i == length)//递归结束的条件
    	{
        
    		for (int j = 0; j < length; ++j)
    		{
        
    			if (x[j] == 1)
    			{
        
    				cout << arr[j] << " ";   // 1 2 3
    			}
    		}
    		cout << endl;
    	}
    	else
    	{
        
    		x[i] = 1;//选择i节点
    		func(arr, i + 1, length, x);//遍历i的左孩子
    
    		x[i] = 0;//不选择i节点
    		func(arr, i + 1, length, x);//遍历i的右孩子
    	}
    }
    int main()
    {
        
    	int arr[] = {
         1,2,3 };// 1 2 3 12 13 23 ...
    	int length = sizeof(arr) / sizeof(arr[0]);
    	int x[3] = {
         0 };
    	func(arr, 0, length, x);
    	return 0;
    }

**时间复杂度：叶子节点的个数**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 13]

## 子集树求解的模板 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**length是数组长度，也就是最后一层叶子节点的层数**  
也可以下面这么写![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/6376db07e3b0409f8aacb8263b8c9621.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/23e2dc2d5a6740259fd8ec88073601a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/4bb61a3df97a40ae9e8151bfacbf0739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/a29329fced2340b9a8eb46b60cd34f77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/10c66f0aea694c9c8384d31c5dc87c11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/7fb77ba173a3460db783581d0ec9371c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/8199bbb330a040a0bd684378615f90c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20220829/f406eca87e5742038f53d6c73ed45425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]: /images/20220829/82ce5c09a3f34566be6e0823f989353b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]: /images/20220829/d9b55754c23d40bcab4401b2c9586dfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 10]: /images/20220829/a02f9ae9c8a24cdebee1d2ffa306ae97.png
[7e403f98173842008f12af598ff9d656.png]: /images/20220829/20558eaf3cae4f8a8b37f2646c184aa1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 11]: /images/20220829/bf9c9e9ca0e0423ba668aa6cb141073f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 12]: /images/20220829/f911665d3aa048adbfc828c706160a60.png
[8e5c5ac88c4a49d891e091d111e1d578.png]: /images/20220829/9cacfe78188d47c4ba1a0b0546afe946.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0bcb19918e7c45ac80cc94cf63b2bb5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 13]: /images/20220829/d36425b7050f401a928cc5974e50a755.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/deece614be074eddbfbad61efa5b84da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/ea3c090471de4f92af674276e5da685f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/ebbdd1caf3cb4dcf91a963f37d6e804f.png