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] ]
Solution: DFS
Time complexity: O(n!)
Space complexity: O(n)
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 |
// Author: Huahua class Solution { public: vector<vector<int>> permute(vector<int>& nums) { const int n = nums.size(); vector<vector<int>> ans; vector<int> used(n); vector<int> path; function<void(int)> dfs = [&](int d) { if (d == n) { ans.push_back(path); return; } for (int i = 0; i < n; ++i) { if (used[i]) continue; used[i] = 1; path.push_back(nums[i]); dfs(d + 1); path.pop_back(); used[i] = 0; } }; dfs(0); return ans; } }; |