康瑞部落

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

解题思路：

回溯法即可。有一个小技巧，先申请一个vector，长度为nums.size()，然后递归调用时采用按引用传递，减少按值传递的开销。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        
        int len = nums.size();
        if(len==0){
            return result;
        }
        
        bool isUse[len];
        memset(isUse, 0, sizeof(bool)*len);
        
        vector<int> item(len);
        
        getPermutations(result, nums, isUse, item, 0);
        
        return result;
    }
    
    void getPermutations(vector<vector<int>>& result, vector<int>& nums, bool* isUse, vector<int>& item, int itemLen){
        if(itemLen==nums.size()){
            result.push_back(item);
        }else{
            for(int i=0; i<nums.size(); i++){
                if(!isUse[i]){
                    isUse[i]=true;
                    item[itemLen] = nums[i];
                    getPermutations(result, nums, isUse, item, itemLen + 1);
                    isUse[i]=false;
                }
            }
        }
    }
};

解题思路2：

晚上和室友听完FB的宣讲会之后，在等公交。谈话中，室友不经意说出一个“交换”二字，于是想到这道题曾经见过交换的解法，非常棒，于是回来立即实现了一番，一次AC。代码如下。下面的代码空间复杂度为O(1)，比上面的办法运行的更快，因为无需判断是否已经使用过某个数。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        
        int len = nums.size();
        if(len==0){
            return result;
        }
        
        getPermutation(nums, result, 0);
        
        return result;
    }
    
    void getPermutation(vector<int>& nums, vector<vector<int>>& result, int start){
        if(start>=nums.size()){
            result.push_back(nums);
        }else{
            for(int i=start; i<nums.size(); i++){
                swap(nums, i, start);
                getPermutation(nums, result, start+1);
                swap(nums, i, start);
            }
        }
    }
    
    void swap(vector<int>& nums, int i, int j){
        if(i==j){
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

二次刷题（2015-08-18）

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<bool> flag(nums.size(), false);
        helper(flag, vector<int>(), nums, result);
        return result;
    }
    
    void helper(vector<bool>& flag, vector<int> item, vector<int>& nums, vector<vector<int>>& result){
        if(item.size() == nums.size()){
            result.push_back(item);
            return;
        }
        for(int i = 0; i<nums.size(); i++){
            if(!flag[i]){
                flag[i]=true;
                item.push_back(nums[i]);
                helper(flag, item, nums, result);
                item.pop_back();
                flag[i] = false;
            }
        }
    }
};