LeetCode:46. Permutations 全排列(C语言)

水深无声 2023-07-03 04:52 26阅读 0赞

**题目描述：**  
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: \[1,2,3\]  
输出:  
\[  
\[1,2,3\],  
\[1,3,2\],  
\[2,1,3\],  
\[2,3,1\],  
\[3,1,2\],  
\[3,2,1\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */
    #define LEN 0xffff
    
    void swap(int*a, int*b)
    { 
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    void rec(int *arr, int len, int index, int **ret, int *ret_index){ 
        int i;
        if(index == len-1)
        { 
            ret[*ret_index] = (int *)malloc(sizeof(int) * len);
            memcpy(ret[*ret_index], arr, len*sizeof(int));
            (*ret_index)++;
            return;
        }
    
        for(i=index; i<len; i++)
        { 
            swap(&arr[i], &arr[index]);
            rec(arr, len, index+1, ret, ret_index);
            swap(&arr[i], &arr[index]);
        }
    }
    
    int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
    { 
        //二维数组
        int **ret = (int **)malloc(sizeof(int*)*LEN); 
        //每行长度 
        int *retSize = (int *)malloc(sizeof(int)*LEN); 
        //行数
        int retIndex = 0;     
        int i = 0;
    
        rec(nums, numsSize, 0, ret, &retIndex);                          
        *returnColumnSizes = retSize;
        for(i = 0; i<retIndex;i++)
        { 
            retSize[i] = numsSize;
        }
    
        *returnSize = retIndex; //行数
    
        return ret;             //返回二维数组
    }

**运行结果：**  
![在这里插入图片描述][20200202153004426.png]  
**Notes：**  
使用递归方法解答。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]  
参考此链接：[https://blog.csdn.net/weixin\_36094222/article/details/90143695][https_blog.csdn.net_weixin_36094222_article_details_90143695]

[20200202153004426.png]: https://img-blog.csdnimg.cn/20200202153004426.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202153029558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg==,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_weixin_36094222_article_details_90143695]: https://blog.csdn.net/weixin_36094222/article/details/90143695