Two ways to find neighbor from a set


  • 0
    N

    The DFS_based Backtracking is obvious for this problem.
    However how to build neighbor of a vertex makes me struggle for a while.
    My first solution is like below:

    Running Time: beats 42.82%

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> solutions;
        vector<int> solution;
        recursion(0, nums, solution, solutions);
        return solutions;
    }
    
    void recursion(int pos, vector<int>& nums, vector<int>& solution, vector<vector<int>>& solutions) {
        // exit condition
        if (pos == nums.size()) {
            solutions.push_back(solution);
            return;
        }
        //recursive calling
        for (int i = 0; i <= solution.size(); i++) {
            solution.insert(solution.begin() + i, nums[pos]);
            recursion(pos + 1, nums, solution, solutions);
            solution.erase(solution.begin() + i);
        }
    }
    

    In each recursion I insert nums[pos] into different index of partial solution. I have to say this approach generates permutations in a weird order, it is [3,2,1], [2,3,1], [2, 1 ,3]... Moreover as we all know it is bad idea to repeatedly do the random insert and erase to vector. So the running time is so slow.

    The second approach would be more natural

    Running time : beats 90.96%

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> solutions;
        vector<int> solution;
        recursion(nums, solution, solutions);
        return solutions;
    }
    
    void recursion(vector<int>& nums, vector<int>& solution, vector<vector<int>>& solutions) {
        // exit condition
        if (solution.size() == nums.size()) {
            solutions.push_back(solution);
            return;
        }
        //recursive calling
        for (int i = 0; i < nums.size(); i++) {
            if (find(solution.begin(), solution.end(), nums[i]) != solution.end())
                continue;
            solution.push_back(nums[i]);
            recursion(nums, solution, solutions);
            solution.pop_back();
        }
    }
    

    We can just add a if condition to see whether nums[i] is already in our vertex. If so, we can't use it to extend our vertext or build the neighbor. In this way, we just apply query operation to vector, which is much faster than dynamic operation.


Log in to reply
 

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