Subsets of a given set

general
, , ,
1

I’ve been trying to find all the subsets of a given set(natural numbers from 1 to n) using backtracking but I could not frame the code for it. I did it using stacks.

Here is the C code for it.

int stack[100],top;
int lim,temp;
int main(){
    top = -1;
    int n;
    printf("\nEnter n:",&n);
    scanf("%d",&n);
    lim=n+1;
    func(1);
    return 0; 
}

int push(int x){
    stack[++top] = x;
    return 0;
}


int pop(){
    if (top!=-1){
        top--;
        return (stack[top+1]);
    }
    else {
        main();
    }
}

int display(){
    int i;
    printf("[ ");
    for (i=0;i<=top;i++) printf("%d ",stack[i]);
    printf("]\n");
}

int func(int x){
    if (x==lim){
        display();
        temp = pop();
        func(temp+1);
    }
    else{
        push(x);
        func(x+1);
    }
}

Can anyone help me with the code for backtracking?

2

Hello,

i usually use bit-masks for checking each subset. but if u only want backtracking then here is the code i usually use for backtracking:

vector< int > btstate;

void BackTrack(int x){       
if(x == lim){

//your subset is in btstate

}

//now each x either comes in subset or not

btstate.push_back(x);

BackTrack(x+1);//x is in subset

btstate.pop_back();//x is not

BackTrack(x+1);

}
1 Like