Print all sub sequences of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub subsequences.

Example:

int [] a = {1, 2, 3};
Output: Possible sub sequences –
{Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2, 3}, {1, 2, 3}

Approach:

  • The approach will be similar to as discussed here Gen­er­ate All Strings of n bits
  • If we consider n= 3(same as the array size) then all possible combinations are [0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1].
  • So from the above combinations, wherever the bit is set to 1, place an array element at the position and wherever the bit is set to 0, ignore the array element.
  • The above step will give the desired result.
  • See the code below for better understanding.

Time Complexity: O(2^n)

Complete Code:



Output:

1 2 3
1 2
1 3
1
2 3
2
3
{Empty Set}

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Ks

    Much simpler code

    public class ArraySubSequences {

    public static void main(String[] args) {

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

    printSubSequences(a, 0, new ArrayList(), ” “);

    }

    static void printSubSequences(int[] arr, int start, List chosen, String space) {

    if(start > arr.length) {
    return;
    }
    else {
    for (int i = start; i < arr.length; i++) {
    //choose
    chosen.add(arr[i]);
    System.out.println(space + chosen);
    //explore
    printSubSequences(arr, i + 1, chosen, space + " ");
    //un-choose
    chosen.remove(chosen.size() – 1);
    }
    }
    }
    }

%d bloggers like this: