C语言基础-leetcode编程题解之第90题子集II.zip

#include <limits.h> #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> static inline int compare(const void *a, const void *b) { return *(int *) a - *(int *) b; } static void dfs(int *nums, int size, int start, int *buf, int level, int **sets, int *count, int *sizes) { int i, last = INT_MIN; sets[*count] = malloc(level * sizeof(int)); memcpy(sets[*count], buf, level * sizeof(int)); sizes[*count] = level; (*count)++; for (i = start; i < size; i++) { if (last != nums[i]) { /* No duplicate candidate elements at same level position */ buf[level] = nums[i]; /* i + 1 limits the selecting range in next levels */ dfs(nums, size, i + 1, buf, level + 1, sets, count, sizes); } last = nums[i]; } } /** ** Return an array of arrays of size *returnSize. ** The sizes of the arrays are returned as *returnColumnSizes array. ** Note: Both returned array and *returnColumnSizes array must be malloced, assume caller calls free(). **/ static int** subsetsWithNoDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { qsort(nums, numsSize, sizeof(int), compare); int capacity = 5000; int **sets = malloc(capacity * sizeof(int *)); int *buf = malloc(numsSize * sizeof(int)); *returnColumnSizes = malloc(capacity * sizeof(int)); *returnSize = 0; dfs(nums, numsSize, 0, buf, 0, sets, returnSize, *returnColumnSizes); return sets; } int main(int argc, char **argv) { int i, j; if (argc <= 1) { fprintf(stderr, "Usage: ./test array...\n"); exit(-1); } int size = argc - 1; int *nums = malloc(size * sizeof(int)); for (i = 0; i < size; i++) { nums[i] = atoi(argv[i + 1]); } int *sizes; int count; int **lists = subsets(nums, size, &count, &sizes); for (i = 0; i < count; i++) { for (j = 0; j < sizes[i]; j++) { printf("%d ", lists[i][j]); } printf("\n"); } return 0; }