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}

3 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.

4 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[0] = 1;
  A[1] = 2;
  A[2] = 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[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

3 Likes

[http://ideone.com/6HD8P9][1]

Visit the above link for recursive code.
[1]: http://ideone.com/6HD8P9

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 :slight_smile:

5 Likes