[leetcode] Permutations

유의할점

swap 이용가능.

풀이

코드

C++ : 내풀이

class Solution {
private:
    bool check[21];
    vector<vector<int>> res;
public:
    void makePermutation(vector<int> &temp, vector<int>& nums){
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return;
        }
        
        for(int i = 0; i < nums.size(); i++){
            if(!check[i]){
                check[i] = true;
                temp.push_back(nums[i]);
                makePermutation(temp, nums);
                temp.pop_back();
                check[i] = false;
            }
        }
        return;
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> temp;
        fill_n(check,21,false);
        makePermutation(temp, nums);
        return res;
    }
};

C++ : swap 이용

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
	    vector<vector<int> > result;
	    
	    permuteRecursive(num, 0, result);
	    return result;
    }
    
    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
	void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
		if (begin >= num.size()) {
		    // one permutation instance
		    result.push_back(num);
		    return;
		}
		
		for (int i = begin; i < num.size(); i++) {
		    swap(num[begin], num[i]);
		    permuteRecursive(num, begin + 1, result);
		    // reset
		    swap(num[begin], num[i]);
		}
    }
};