leetcode46.全排列

Posted on | In |
Words count in article: 216 | Reading time ≈ 1

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

分析：

1
2
3
DFS：
搜索顺序：按位置从0开始搜索
剪枝：st[i]表示字符是否被使用过

代码

  • C++

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permute(vector<int>& nums) {
        st.resize(nums.size());
        dfs(0, nums.size(), nums);

        return res;
    }

    void dfs(int u, int n, vector<int>& nums) {
        if (u == n) {
            res.push_back(path);
            path.empty();
            return;
        }

        for (int i = 0;i < n;i ++) {
            if (st[i]) continue;
            st[i] = true;
            path.push_back(nums[i]);
            dfs(u + 1, n, nums);
            st[i] = false;
            path.pop_back();
        }

    }
};

[原题链接](46. 全排列 - 力扣（Leetcode）)

0%