欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)

程序员文章站 2022-07-15 19:03:02
...

【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)

题目

给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解一、递归回朔法

类似 树的中序遍历方法。

【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)

命令行打印输出结果,和上面推导一样,我画成树后,如下:

					  交换 11   				内容:[1,2,3]  first = 1
					 |-------交换 22   			内容:[1,2,3]  first = 2
					 |		|-------交换 33   	内容:[1,2,3]  first = 3	====> 输出
					 |	
					 |-------交换 23 			内容:[1,3,2]  first = 2
						 	|-------交换 22   	内容:[1,3,2]  first = 3	====> 输出
					
					 交换 12 					内容:[2,1,3]  first = 1
					 |-------[2,1,3] 交换 11   	内容:[2,1,3]  first = 2
数组内容:[1,2,3]	 |		|-------交换 33   	内容:[2,1,3]  first = 3	====> 输出
					 |	
					 |-------交换 13 			内容:[2,3,1]  first = 2
					 |		|-------交换 11 	内容:[2,3,1]  first = 3	====> 输出
					
					 交换 13  					内容:[3,2,1]  first = 1
					 |-------[2,1,3] 交换 22  	内容:[3,2,1]  first = 2
					 |		|-------交换 11  	内容:[3,2,1]  first = 3	====> 输出
					 |	
					 |-------交换 21  			内容:[3,1,2]  first = 2
					 |		|-------交换 22  	内容:[3,1,2]  first = 3	====> 输出

代码如下:


// 方法一、递归回朔法
class Solution {
public:
/*
    void print( vector<int> &nums){
        cout << " 数组内容:[";
        for(int i = 0; i<nums.size(); i++){
            cout << nums[i];
            if(i != nums.size()-1){
                cout << ",";
            }else{
                cout << "]";
            }
        }
    }
*/
    void backtrace(vector<vector<int>> &result, vector<int> &nums, int first, int size){
        if(first == size){
            result.emplace_back(nums);
            return;
        }else{
            for(int i = first; i<size; i++){
                //cout << " 交换 "<< nums[first] << " 和 " << nums[i];
                swap(nums[i], nums[first]); // 交换第一个数 与 当前数

                //print(nums);
                //cout <<  "  first = " << first + 1 << endl;

                backtrace(result, nums, first+1, size);

                swap(nums[first], nums[i]); // 还原现场
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrace(result, nums, 0, nums.size());
        return result;
    }
};

【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)


题解二、非递归实现

利用 《【LeetCode #31 题解】 下一个排列》中的解法,不停的求解下一个排列,
直到求解到最大值就可以了。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());			// 排序成升序,即最小排列
        result.push_back(nums);

        while(true){
            int pos = nums.size() - 1; 
            cout << "数组大小为:"<< pos + 1 << endl;

            // 1. 从末尾寻找第一个破坏降序的数
            while(pos > 0 && nums[pos] <= nums[pos-1])
                pos--;
            
            // 2. 找到第一个比它大的数,交换
            if(pos > 0){
                cout << "找到数字为: pos="<<pos-1 << " num="<<nums[pos-1] << endl;
                
                for(int i = nums.size()-1 ; i>=pos ; i--){
                    if(nums[i] > nums[pos-1]){
                        cout << "交换" <<nums[pos-1] << "和" << nums[i]<< endl; 
                        swap(nums[pos-1], nums[i]);
                        break;
                    }
                }
            }else
                break;

            // 3. 升序排列
            reverse(nums.begin() + pos, nums.end());
            result.push_back(nums);
        }
        
        return result;
    }
};

输出结果为:
从结果,可以看出,求解全排列,
就是从最小排列[1,2,3,4],一直求下一排列,直到最大排列[4,3,2,1]的过程。

[1,2,3,4],
[1,2,4,3],
[1,3,2,4],
[1,3,4,2],
[1,4,2,3],
[1,4,3,2],
[2,1,3,4],
[2,1,4,3],
[2,3,1,4],
[2,3,4,1],
[2,4,1,3],
[2,4,3,1],
[3,1,2,4],
[3,1,4,2],
[3,2,1,4],
[3,2,4,1],
[3,4,1,2],
[3,4,2,1],
[4,1,2,3],
[4,1,3,2],
[4,2,1,3],
[4,2,3,1],
[4,3,1,2],
[4,3,2,1]

【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)