算法

全排列

Posted by Liao on 2020-02-24

全排列涉及循环和递归。递归由递归关系式和递归出口组成。

在每一次循环中，可以从左到右确定一个数字，然后通过递归让剩下k-1个数进行全排列。

也可以从右到左，先确定最后一个数字，然后把前面k-1个数字进行全排列。

Leetcode

输入: [1,2,3]

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

思路一：确定第一个数字，对后k-1个数字进行全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> res;
    void perm(vector<int>nums, int p, int q)
    {
        if(q == p)//递归出口
        {
            res.push_back(nums);
            return;  //每次排列完之后，返回到函数末尾，之后执行还原数组的第二个交换代码
        }
        else
        {
            for(int i = p; i < q; i++)
            {
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
                
                perm(nums,p+1,q);
                
                //递归把剩下的k-1个数全排列时，要把数列还原，防止重复
                //执行递归出口之后执行此处
                temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
            }
        }
    }//末尾
    vector<vector<int>> permute(vector<int>& nums) {
        int len = nums.size();
        perm(nums,0,len);
        return res;
    }
};

思路二：确定最后一个数字，前k-1个数字进行全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> res;
    void perm(vector<int>nums, int q)
    {
        if(q == 1)//递归出口
        {
            res.push_back(nums);
            return;
        }
        else
        {
            for(int i = 0; i < q; i++)
            {
                int temp = nums[i];
                nums[i] = nums[q-1];
                nums[q-1] = temp;
                
                perm(nums,q-1);
                
                temp = nums[i];
                nums[i] = nums[q-1];
                nums[q-1] = temp;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int len = nums.size();
        perm(nums,len);
        return res;
    }
};
FEATURED TAGS
算法
FRIENDS