LeetCode 46 全排列 permutations

LeetCode 46 全排列

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

Example

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

解题思路

求全排列问题，用递归 DFS 来求解。这里需要用到一个 visited 数组来标记某个数字是否访问过，然后在 DFS 递归函数从的循环应从头开始， level 记录当前已经拼出的个数，一旦其达到了 nums 数组的长度，说明此时已经是一个全排列了。这个和77题 Combinations 组合项不太一样，这里 level 从0开始遍历，因为这是求全排列，每个位置都可能放任意一个数字，然而不能重复使用数字，这里用了visit数组来标记是否使用过

AC 代码

vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> out;int n = nums.size();vector<int> visit(n, 0);dfs(res, out, 0, visit,nums);return res;}void dfs(vector<vector<int>>& res, vector<int>& out, int level, vector<int>& visit, vector<int>& nums){if (level == nums.size()){res.push_back(out);return;}for (int i = 0; i < nums.size(); ++i){if (visit[i] == 1)continue;out.push_back(nums[i]);visit[i] = 1;dfs(res, out, level + 1, visit, nums);visit[i] = 0;out.pop_back();}}

如果对您有所启发，请给我的repo一个star吧！