// 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]); }