print all possible subsequences of string using dynamic programming

general
1

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
2

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
3

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
4

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

4 Likes
5

[6HD8P9 - Online C++ Compiler & Debugging Tool - Ideone.com][1]

Visit the above link for recursive code.
[1]: 6HD8P9 - Online C++ Compiler & Debugging Tool - Ideone.com

6

can you please elaborate your code!

7

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

8

What if all the value are repeating

9

// 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

10

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

15

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

5 Likes