For someone who does not like recursion. C++ Solution


  • 0
    S

    The basic idea is like inserting the new element in all the possible position.
    1: 1
    2: 21 12 (insert 2 at 0 and 1)
    3: 321 231 213 (insert 3 to 21) 312 132 123 (insert 3 to 12)
    and so on.
    The idea can be implement in many ways. Since I don't like recursion, (which means I'm not good at recursion) so here is the way to implement with a queue.

    class Solution {
    public:
        void print(vector<int> tmp){
            for(int i = 0; i < tmp.size(); i++){
                cout << tmp[i] << " ";
            }
            cout << endl;
        }
        vector<vector<int>> permute(vector<int>& nums) {
            int size1 = nums.size(), count = 1;
            vector<vector<int>> result;
            if(size1 == 0) return result;
            vector<int> cur(1,nums[0]);
            queue<vector<int>> store;
            store.push(cur);
            
            while(count < size1){
                int size2= store.size(), i = 0;
                while(i < size2){
                    cur = store.front();
                    store.pop();
                    int size3= cur.size();
                    for(int j = 0; j <= size3; j++){
                        auto it = cur.insert(cur.begin() + j, nums[count]);
                        //print(cur);
                        store.push(cur);
                        cur.erase(it);
                    }
                    i++;
                }
                count++;
            }
            while(!store.empty()){
                result.push_back(store.front());
                store.pop();
            }
            return result;
        }
    };
    

Log in to reply
 

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