how can we print all possible subsequences of string using dynamic programming.

for ex . for sequence 1,2,3

the possible subsequences are {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

for(i=1;i<1<<n;i++)

{

for(j=1;j<=n;j++)

{

if((1<<j)&i)

{

printf("%d\n",a[j]);

}

}

}

provided all the elements of sequence are unique.

There is not DP solution to that problem, you are asking to generate all possible subsets(Power Set), since all subsets are unique overlap doesn’t exist and DP can’t be used. You have to use exhaustive search.

```
#define MAX 20
int n; // Number of elements in A
int A[MAX];
bool V[MAX];
void subsets(int i)
{
if (i == n) {
for (int j = 0; j < n; j++)
if (V[j])
printf("%d ", A[j]);
printf("\n");
} else {
// Each element of the original set may be or not in the subsets
// Since each element has two options the total number subsets is:
// 2 * 2 * 2 * ... * 2 = 2^n
// -------------------------
// 1 2 3 ... n
V[i] = true; // This element will be in the subset
subsets(i + 1);
V[i] = false; // This element won't be in the subset
subsets(i + 1);
}
}
```

How to use:

```
A[0] = 1;
A[1] = 2;
A[2] = 3;
n = 3;
subsets(0);
```

The complexity of this algorithm is 2^{n} where `n`

is the number of elements in `A`

.

The algorithm generate 2^{n} subsets, including the empty set `{}`

.

int a[]={1,2,3};

int n=sizeof(a)/sizeof(a[0]);

for(int i=1; i<1<<n; i++)

{

int temp=i;

int j=0;

while(temp)

{

if (temp&1) // if jth bit is set print a[j]

{

printf("%d “,a[j]);

}

temp >>= 1;

j++;

}

printf(”\n");

}

output

1

2

1 2

3

1 3

2 3

1 2 3

can you please elaborate your code!

also I think you should place your ‘\n’ outside the inner loop!

What if all the value are repeating

// O (n * (2 ^ n))

string s = “abc”;

int n = s.length();

for(int i=1; i<(1<<n); i++) {

for(int j=0; j<n; j++) {

if((1<<j) & i) cout << s[j];

}

cout << ‘\n’;

}

output:

a

b

ab

c

ac

bc

abc

It is called Bitmasking you can search it on Google and you will get it

NB: Deleted four posts in this ancient thread as they were moving it off-topic and towards a rule violation