#define MAX_K 100 void subset_rec( const char *cont, const size_t start, const size_t n, char *res, const size_t last) { size_t i; // print (res, last); for (i = start; i < n; i++) { res[last] = cont[i]; subset_rec(cont, i+1, n, res, last+1); } } void subset(const char *content, const size_t n) { char *result; result = (char*)malloc(MAX_K * sizeof(char)); subset_rec(content, 0, n, result, 0); free(result); result = NULL; } void comb_rec( const char *cont, // pointer to combination's content const size_t start, // starting index of the content const size_t n, // n of C(n,k) const size_t k, // k of C(n,k) char *res, // pointer to one combination generated so far const size_t last) // length of the result { size_t i; if (k == 0) { // print (res, last); } else { for (i = start; i < n; i++) { res[last] = cont[i]; comb_rec(cont, i+1, n, k-1, res, last+1); } } } void combination(const char *content, const size_t n, const size_t k) { char *result; if (k > n || k == 0 || n == 0) return; result = (char*)malloc(MAX_K * sizeof(char)); comb_rec(content, 0, n, k, result, 0); free(result); result = NULL; } void perm_rec( char *cont, const size_t n, const size_t k, char *res, const size_t last) { size_t i; char t; if (k == 0) { // print (res, last); } else { for (i = 0; i < n; i++) { t = cont[i]; res[last] = t; // A B C D memmove(cont+i, cont+i+1, n-i-1); // A C D perm_rec(cont, n-1, k-1, res, last+1); memmove(cont+i+1, cont+i, n-i-1); // A A C D cont[i] = t; // A B C D } } } void permutation(const char *content, const size_t n, const size_t k) { char *result; if (k > n || k == 0 || n == 0) return; result = (char*)malloc(MAX_K * sizeof(char)); perm_rec((char*)content, n, k, result, 0); free(result); result = NULL; }
For the permutation of set that contains duplicates, the solution can be found here:
https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c
No comments:
Post a Comment
(Coding && Eating) || Sleeping