Blog Archives

It’s recursive, it’s coded on C, it has dynamic memory allocation(and it frees it after using!). Check it out,

#include <stdio.h>
#include <stdlib.h>

#define TYPE unsigned char

int n, r, out_count=0;

typedef struct st_node {
    TYPE data;
    struct st_node *parent;
}node;

node *new_node(node *p){
    node *new = malloc(sizeof(node));
    new->parent = p;
    return new;
}
void back_track(node *child){
    while (child != NULL){
        printf(" %d", child->data);
        child = child->parent;
    }
    printf("n");
    out_count++;
}
int check_used(node *child, TYPE a){
    while (child != NULL){
        if (a == child->data)
            return 1;
        child = child->parent;
    }
    return 0;
}
void perm( int i, node *parent, int count){
    int j;
    if (count == r){
        back_track(parent);
        return;
    }

    for (j=0;j<n;j++){
        if (check_used(parent,(TYPE) j) == 1)
            continue;
        node *child = new_node(parent);
        child->data=j;

        perm( j, child, count + 1);
        free(child);
    }
}

void comb( int i, node *parent, int count){
    int j;
    if (count == r){
        back_track(parent);
        return;
    }

    for (j=i+1;j<=n;j++){
        if (n-j < r-count-1)
            break;
        node *child = new_node(parent);
        child->data=j-1;

        comb( j, child, count + 1);
        free(child);
    }
}
int main(){
    scanf("%d",&n);
    scanf("%d",&r);

    perm(0,NULL,0);
    //comb(0,NULL,0);
    printf("Count: %dn",out_count);
    return 0;
}