难度:Medium
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 {vector<vector<int>>res;void traceback(int n, int step){if(step == n) return;int len=res.size();for(int i=0;i<len;i++){for(int j=step+1;j<n;j++){vector<int> tmp(res[i]);swap(res[i][step],res[i][j]);res.push_back(tmp);}}traceback(n,step+1);}public:vector<vector<int>> permute(vector<int>& nums) {res.push_back(nums);traceback(nums.size(), 0);return res;}};
执行用时 :12 ms, 在所有 C++ 提交中击败了98.71%的用户 内存消耗 :9.7 MB, 在所有 C++ 提交中击败了29.71%的用户