418-回溯算法-基于穷举法的全排列实现

末蓝、 2022-09-05 01:53 196阅读 0赞

## 基于穷举法的全排列实现 ##

**另一种实现全排列的代码 满足leetcode刷题测试用例**

**力扣的题目：输出123的全部排列**  
**力扣要求的输出结果如下：**  
![在这里插入图片描述][ad46822b24bd4787b8a3c4c2d196ff16.png]  
**但是如果我们用之前的排列树输出的如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

**满足力扣的输出示例的代码如下：**  
**暴力枚举法：每个位置都有机会去选择所有的可能出现的元素**  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
这里的树是绝对平衡的，因为是全排列，每个序列的深度是一样的。  
**满足O(n!)**  
**这也是排列树**  
**用的是穷举法，元素的选择。**  
**1、选择数字 ，定义一个vec用来实时的保存数字，回溯时再删除数字。**  
**2、一个节点可以选择的其他元素（这个节点可以选除了选过的所有元素）**  
**我们需要定义一个state\[3\]记录元素1，元素2，元素3的状态**  
从根节点向叶子节点遍历的过程中，节点是否被选择的状态，选择2了，把2的对应的位置置为true，选择1了，把1对应的位置置为true，然后看哪个元素对应的位置是false，就可以继续选择。从state\[0\]开始遍历，选择第一个值为false的对应元素，以此类推。

## 基于穷举法的全排列代码实现 ##

**k：表示的是可选择的元素的起始下标 i：表示层数**

int ar[] = {
         1,2,3 };
    const int N = 3;
    bool state[N];//记录所有元素是否被选择的状态  true：选择了  false：未选择
    vector<int> vec;
    void func(int i)//排列树
    {
        
    	if (i == N)//到达叶子节点了
    	{
        
    		for (int v : vec)
    		{
        
    			cout << v << " ";
    		}
    		cout << endl;
    	}
    	else
    	{
        
    		for (int k = 0; k < N; ++k)//k=0是因为所有元素都可以出现，所以每次递归调用都是从k=0进行判断，都是从数组的0号位置开始找没有被选择的数字
    		{
        
    			if (!state[k])//该元素没有被选择
    			{
        
    				state[k] = true;//选择了
    				vec.push_back(ar[k]);
    				func(i + 1);//k：表示的是可选择的元素的起始下标  i：表示层数
    				vec.pop_back();//回溯到父节点
    				state[k] = false;
    			}
    		}
    	}
    }
    int main()
    {
        
    	func(0);
    	return 0;
    }

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

[ad46822b24bd4787b8a3c4c2d196ff16.png]: /images/20220829/cca5eecdb5914df1bc716dedd85a8f37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/60b92f17261d46b6b7015dd19c33099a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/4869f43391ad471c9474129510348232.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/1e403ac45c8848479e09f9cd2067c474.png
[a73fa6dca43249f8bb7efe7aa2b1bb69.png]: /images/20220829/7770b0f4542a4bd0bd4049417b1d4f1d.png