来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
- 输入: [1,2,3]
- 输出:
1 2 3 4 5 6 7 8 |
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,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 35 36 37 38 39 40 |
class Solution { private: set<int> m_set; vector<int> m_vec; vector<vector<int>> m_res; void dfs(vector<int> &nums, int l, int r) { int i; if (l == r) { m_res.push_back(m_vec); return; } for (i = 0; i < nums.size(); i++) { set<int>::iterator it; if (m_set.find(nums[i]) != m_set.end()) continue; // 没有找到 m_vec.push_back(nums[i]); m_set.insert(nums[i]); // 深搜 dfs(nums, l + 1, r); // 删除当前值,遍历下一个节点 m_vec.pop_back(); it = m_set.find(nums[i]); if (it == m_set.end()) throw logic_error("cannot find key"); m_set.erase(it); } } public: vector<vector<int>> permute(vector<int> &nums) { dfs(nums, 0, nums.size()); return m_res; } }; |
评论