Subsets

permute.cpp

//Iteration
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    queue<vector<int>> q;
    q.push(vector<int>());
    for(auto num : nums){
        // we will take all existing permutations and add the current number to create new
        // permutations
        int n = q.size();
        for(int i = 0; i < n; i++){
            vector<int> lastPerm = q.front();
            q.pop();
            // create a new permutation by adding the current number at every position
            // to add at EACH position, we need <= lastPerm.size(), i.e. the number of positions is size+1, [1,3]=>[x1x3x]
            for(int j = 0; j <= lastPerm.size(); j++){
                vector<int> newPerm(lastPerm);
                newPerm.insert(newPerm.begin()+j, num);
                if(newPerm.size() == nums.size())
                    res.push_back(newPerm);
                else
                    q.push(newPerm);
            }
        }
    }
    return res;
}

// Iteration, simple version
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res{{}};
    for (int num : nums) {
        for (int i = res.size(); i > 0; i--) { //start with size, so it won't be affected by the change on res in loop.
            vector<int> lastPerm = res.front(); //last permutation without current element
            res.erase(res.begin());
            for (int j = 0; j <= lastPerm.size(); j++) {
                vector<int> newPerm = lastPerm;
                newPerm.insert(newPerm.begin() + j, num);
                res.push_back(newPerm);
            }
        }
    }
    return res;
}

//Recursion
void permuteRec(vector<int>& nums, int idx, vector<int>& currentPerm, vector<vector<int>>& res){
    if(idx == nums.size())
        res.push_back(currentPerm);
    else{
        for(int i = 0; i <= currentPerm.size(); i++){
            vector<int>newPerm(currentPerm);
            newPerm.insert(newPerm.begin()+i, nums[idx]);
            permuteRec(nums, idx+1, newPerm, res);
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> currentPerm;
    permuteRec(nums, 0, currentPerm, res);
    return res;
}