LeetCode/46. Permutations.cpp at master · ChanDaoH/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
46. Permutations
*/

#include<stdio.h>
#include<stdlib.h>
void helper(int* nums, int numsSize, int* s, int count, int* subset, int* size, int** res);
int** permute(int* nums, int numsSize, int* returnSize) {
    int **res,*subset,*s;
    int size,count;

    size=count=0;
    res = (int**)malloc(sizeof(int*)*100);
    subset = (int*)malloc(sizeof(int)*numsSize);
    s = (int*)malloc(sizeof(int)*numsSize);
    for( int i = 0; i < numsSize; i++ ){
		s[i] = 0;
    }

    helper(nums,numsSize,s,count,subset,&size,res);

    *returnSize = size;
    return res;
}

void helper(int* nums, int numsSize, int* s, int count, int* subset, int* size, int** res)
{
	int i;
	if( count == numsSize ){
		int k = *size;
		*(res+k) = (int*)malloc(sizeof(int)*count);
		for( i = 0; i < count; i++ ){
			res[k][i] = subset[i];
		}
		(*size)++;
		return;
	}
	for( i = 0; i < numsSize; i++ ){
		if( !s[i] ){
			subset[count++] = nums[i];
			s[i] = 1;
			helper(nums,numsSize,s,count,subset,size,res);
			count--;
			s[i] = 0;
		}
	}
}

int main()
{
	int nums[3] = {1,2,3};
	int numsSize = 3;
	int size;
	int **res;
	res = permute(nums,numsSize,&size);
	for( int i = 0; i < size; i++ ){
		for( int j = 0; j < numsSize; j++ ){
			printf("%d\t",res[i][j]);
		}
		printf("\n");
	}
}