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] ]求全排列。
思路：递归+深度优先搜索
因为排列要使用所有数，这里，我们使用一个标记信号，记录这个数用过了没有。
最后，别忘了回溯。
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ans; vector<int> cur; vector<bool> mark(nums.size(),false); sort(nums.begin(), nums.end()); dfs(nums, 0, ans, cur,mark); return ans; } void dfs(vector<int>& nums, int num, vector<vector<int >>& ans, vector<int>& cur, vector<bool>& mark) { if (num == nums.size()) {//排完了，存入 ans.push_back(cur); } for (int i = 0; i < nums.size(); i++) {//每一次都从0开始搜索，遍历所有的数 if (mark[i] == false) {//标记信号，这个数在不在cur里，不在，就存入 cur.push_back(nums[i]); mark[i] = true;//说明这个数被用过了 dfs(nums, num + 1, ans, cur,mark); cur.pop_back();//回溯 mark[i] = false; } } } };