Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.4 kB
1
Indexable
Never
class Solution {// swap 
public:
    void solve(int i,vector<vector<int>>&res,vector<int>&nums){
        if(i==nums.size()){
            res.push_back(nums);
        }

        for(int j=i;j<nums.size();j++){
            swap(nums[i],nums[j]);
            solve(i+1,res,nums);
            swap(nums[i],nums[j]);
        }


    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int>ans;
        vector<vector<int>>res;
        solve(0,res,nums);
        return res;
    }
};

class Solution { //BACKTRACKING, i is useless and just for mental understanmding
public:
    void solve(int i,vector<int>&nums,vector<int>&ans,vector<vector<int>>&res,vector<bool>&used){// 
        if(ans.size()==nums.size()){
            res.push_back(ans); // dont return if using backtracking lies after return
            return;
        }

        for(int j=0;j<nums.size();j++){
            if(!used[j]) {
                ans.push_back(nums[j]);
                used[j]=true;
            
                solve(i+1,nums,ans,res,used);

                used[j]=false;
                ans.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> ans;
        vector<bool>used(nums.size(),0);
        solve(0,nums,ans,res,used);
        return res;
    }
};