题目描述

[MEDIUM]

Given a collection of distinct integers, return all possible permutations.

Example 1:

1
2
Input: [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

1
2
Input: [0,1]
Output: [[0,1],[1,0]]

Example 3:

1
2
Input: [1]
Output: [[1]]

思路

递归回溯 （backtracking）

题目要求输出所有不重复的排列。
我们可以使用 回溯（Backtracking）：

  1. 用一个数组 path 来保存当前的排列。

  2. 用一个布尔数组 used 标记哪些数字已经被使用。

  3. 当 path 的长度等于 nums.size() 时，将当前排列加入结果集。

  4. 否则，遍历所有数字：

    • 若该数字未被使用，则加入路径；

    • 递归调用；

    • 回溯（撤销选择）。

代码

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
class Solution {
public:
    vector<vector<int>> re;

    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used){
        if(path.size() == nums.size()){
            re.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, path, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(), false);

        backtrack(nums, path, used);
        return re;
    }
};