 # print all possible subsequences of string using dynamic programming

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}

2 Likes

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.

2 Likes

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 = 1;
A = 2;
A = 3;
n = 3;

subsets(0);
``````

The complexity of this algorithm is 2n where `n` is the number of elements in `A`.

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

4 Likes

int a[]={1,2,3};
int n=sizeof(a)/sizeof(a);
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

1 Like