Sharing my short C++ solution using dfs, modified from Permutation I


  • 2
    H

    The idea is to first sort the list and then use dfs to set the number on each position in the permutation consecutively. When the last number in the permutation is determined, push the permutation into the result. The solution takes O(1) space.

    class Solution {
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            int n = num.size();
            vector<vector<int>> res;  
            sort(num.begin(), num.end());    //sort the list
            permuteUnique(num, res, n, 0);
            return res;
        }
        void permuteUnique(vector<int> &num, vector<vector<int>> &res, int n, int s) {
            if (s == n) {
                res.push_back(num); 
                return;
            }
            for (int j = s; j < n; j++) {
                if (j > s & num[j] == num[j-1]) continue;    //prevent duplicates
                move(num, j, s);    //set the s-th element in the permutation to be 
                                    //num[j], while leaving the rest elements sorted
                permuteUnique(num, res, n, s+1);
                move(num, s, j);    //reset
            }
        }
        void move(vector<int> &num, int j, int i) { 
            num.insert(num.begin() + i + (i > j), num[j]);
            num.erase(num.begin() + j + (j > i));
        }
    };

  • 0
    S
    This post is deleted!

  • 0
    S

    Concise solution. It can be further improved: drop int n, because n = num.size()
    Doing insert/erase in move is not efficient for vector, any better way to do so?


  • 0
    C

    This move function is O(n), isn't it?
    Then the complexity of this method is no longer O(n!).


Log in to reply
 

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