46. 全排列 - 力扣(Leetcode)
题解
思路:DFS
- 注意:力扣测试数据时不会将全局变量重置,要手动重置
C代码
int ptr_line = 0;
int mark[6];
void deep_find(int depth, int* nums, int** ans, int numsSize, int* temp, int size) {
for (int i = 0; i < numsSize; i++) {
if (!mark[i]) {
temp[depth] = nums[i];
mark[i] = true;
if (depth < numsSize - 1)
deep_find(depth + 1, nums, ans, numsSize, temp, size);
else
memcpy(ans[ptr_line++], temp, sizeof(int) * numsSize);
mark[i] = false;
}
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int size = 1;
ptr_line = 0;//全局变量要重置
for (int i = 2; i <= numsSize; i++)
size *= i;
*returnSize = size;
*returnColumnSizes = (int*)malloc(sizeof(int) * size);
int** ans = (int**)malloc(sizeof(int*) * size);
int* temp = (int*)malloc(sizeof(int) * numsSize);
for (int i = 0; i < size; i++) {
(*returnColumnSizes)[i] = numsSize;
ans[i] = (int*)malloc(sizeof(int) * numsSize);
}
deep_find(0, nums, ans, numsSize, temp, size);
return ans;
}
测试函数
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
int nums[5] = { 1, 2, 3, 4, 5 };
int** ans = permute(nums, 5);
for (int i = 0; i < 120; i++)
printf("%d %d %d %d %d\n", ans[i][0], ans[i][1], ans[i][2], ans[i][3], ans[i][4]);
system("pause");
return 0;
}
标签:numsSize,temp,nums,46,题解,mark,int,ans,LeetCode
From: https://www.cnblogs.com/fjnhyzCYL/p/16895496.html