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

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

题目

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

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

题解一、递归回朔法

类似 树的中序遍历方法。

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

					  交换 1 和 1   				内容：[1,2,3]  first = 1
					 |-------交换 2 和 2   			内容：[1,2,3]  first = 2
					 |		|-------交换 3 和 3   	内容：[1,2,3]  first = 3	====> 输出
					 |	
					 |-------交换 2 和 3 			内容：[1,3,2]  first = 2
						 	|-------交换 2 和 2   	内容：[1,3,2]  first = 3	====> 输出
					
					 交换 1 和 2 					内容：[2,1,3]  first = 1
					 |-------[2,1,3] 交换 1 和 1   	内容：[2,1,3]  first = 2
数组内容：[1,2,3]	 |		|-------交换 3 和 3   	内容：[2,1,3]  first = 3	====> 输出
					 |	
					 |-------交换 1 和 3 			内容：[2,3,1]  first = 2
					 |		|-------交换 1 和 1 	内容：[2,3,1]  first = 3	====> 输出
					
					 交换 1 和 3  					内容：[3,2,1]  first = 1
					 |-------[2,1,3] 交换 2 和 2  	内容：[3,2,1]  first = 2
					 |		|-------交换 1 和 1  	内容：[3,2,1]  first = 3	====> 输出
					 |	
					 |-------交换 2 和 1  			内容：[3,1,2]  first = 2
					 |		|-------交换 2 和 2  	内容：[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 #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]