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> permute(vector& nums) {
        vector> result;
        
        int len = nums.size();
        if(len==0){
            return result;
        }
        
        bool isUse[len];
        memset(isUse, 0, sizeof(bool)*len);
        
        vector item(len);
        
        getPermutations(result, nums, isUse, item, 0);
        
        return result;
    }
    
    void getPermutations(vector>& result, vector& nums, bool* isUse, vector& item, int itemLen){
        if(itemLen==nums.size()){
            result.push_back(item);
        }else{
            for(int i=0; i
解题思路2：
晚上和室友听完FB的宣讲会之后，在等公交。谈话中，室友不经意说出一个“交换”二字，于是想到这道题曾经见过交换的解法，非常棒，于是回来立即实现了一番，一次AC。代码如下。下面的代码空间复杂度为O(1)，比上面的办法运行的更快，因为无需判断是否已经使用过某个数。
class Solution {
public:
    vector> permute(vector& nums) {
        vector> result;
        
        int len = nums.size();
        if(len==0){
            return result;
        }
        
        getPermutation(nums, result, 0);
        
        return result;
    }
    
    void getPermutation(vector& nums, vector>& result, int start){
        if(start>=nums.size()){
            result.push_back(nums);
        }else{
            for(int i=start; i& 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> permute(vector& nums) {
        vector> result;
        vector flag(nums.size(), false);
        helper(flag, vector(), nums, result);
        return result;
    }
    
    void helper(vector& flag, vector item, vector& nums, vector>& result){
        if(item.size() == nums.size()){
            result.push_back(item);
            return;
        }
        for(int i = 0; i

 
转载请注明： » [LeetCode] Permutations

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->