C++ 16ms DFS solution (place one at a time for each position)


  • 0
    G
    class Solution {
        void dfs(vector<vector<int>>& ret, vector<int>& pre, vector<int>& cur) {
            if(pre.empty()) {
                return;
            }
            else {
                for(int i = 0; i < pre.size(); i++) {
                    int n = pre.back();
                    cur.push_back(n);
                    pre.pop_back();
                    if(pre.empty()) {
                        ret.push_back(cur);
                    }
                    dfs(ret, pre, cur);
                    pre.insert(pre.begin(), n);
                    cur.pop_back();
                }
            }
        }
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>> ret;
            if(nums.empty()) return ret;
            vector<int> cur;
            dfs(ret, nums, cur);
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.