You are not logged in. Please login at www.codechef.com to post your questions!

×

Subsets of a given set

0
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?

asked 20 Jun '15, 22:49

prrateekk's gravatar image

3★prrateekk
534216
accept rate: 12%

edited 20 Jun '15, 22:50


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

link

answered 20 Jun '15, 23:12

masterss's gravatar image

0★masterss
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,657
×160
×104
×26

question asked: 20 Jun '15, 22:49

question was seen: 1,237 times

last updated: 20 Jun '15, 23:54