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
63
64
65
66
67
68
69
70
71
72
73
74
75
|
// 491. Non-decreasing Subsequences
#include "leetcode.h"
/*
* given: integer array 'nums'
* return: all possible different non-decreasing subsequences
* of given array with at least two elements. return value can be in any order
*/
int **ans, ansTop, *path, pathTop, *len;
bool find_used(int *uset, int usetSize, int key) {
for (int i = 0; i < usetSize; i++)
if (uset[i] == key)
return true;
return false;
}
void backtrack(int *nums, int numsSize, int startIdx) {
if (pathTop >= 2) {
int *tmp = (int *)malloc(pathTop * sizeof(int));
for (int i = 0; i < pathTop; i++)
tmp[i] = path[i];
len[ansTop] = pathTop;
ans[ansTop++] = tmp;
}
int *uset = (int *)malloc(numsSize * sizeof(int)), usetTop = 0;
for (int i = startIdx; i < numsSize; i++) {
if (pathTop > 0 && nums[i] < path[pathTop - 1] ||
find_used(uset, usetTop, nums[i]))
continue;
uset[usetTop++] = nums[i];
path[pathTop++] = nums[i];
backtrack(nums, numsSize, i + 1);
pathTop--;
}
}
int **findSubsequences(int *nums, int numsSize, int *returnSize,
int **returnColumnSizes) {
ans = (int **)malloc(10000 * sizeof(int *));
path = (int *)malloc(numsSize * sizeof(int));
len = (int *)malloc(10000 * sizeof(int));
pathTop = 0;
ansTop = 0;
backtrack(nums, numsSize, 0);
*returnSize = ansTop;
*returnColumnSizes = (int *)malloc(ansTop * sizeof(int));
for (int i = 0; i < ansTop; i++)
(*returnColumnSizes)[i] = len[i];
return ans;
}
int main() {
int n1[] = {4, 6, 7, 7}, n2[] = {4, 4, 3, 2, 1};
int rs1, rs2, *rcs1, *rcs2;
int **fs1 = findSubsequences(n1, ARRAY_SIZE(n1), &rs1, &rcs1);
int **fs2 = findSubsequences(n2, ARRAY_SIZE(n2), &rs2, &rcs2);
for (int i = 0; i < rs1; i++) {
for (int j = 0; j < *rcs1; j++)
printf("%d ", fs1[i][j]);
printf("\n");
}
printf("\n");
for (int i = 0; i < rs2; i++) {
for (int j = 0; j < *rcs2; j++)
printf("%d ", fs2[i][j]);
printf("\n");
}
printf("\n");
for (int i = 0; i < rs1; i++)
free(fs1[i]);
for (int i = 0; i < rs2; i++)
free(fs2[i]);
}
|