Backtracking

Print All Subsequences of an Array

Problem Statement:

You are given an array of integers, and the task is to print all the subsequences (non-contiguous subsets) of the array. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The program should print each subsequence on a new line, excluding the empty subsequence.

Input:

An integer array arr[] of length n.

Output:

Print all subsequences of the array arr[], each subsequence on a new line. Each subsequence should be represented as a list of integers.
Do not print the empty subsequence.

Example:

Input:

arr = {1, 2}

Output:

[1]

[2]

[1, 2]

import java.util.*;

class Solution1{

public static void PrintSequences(int arr[],int index,ArrayList<Integer> tempArr){

if(index==arr.length){

if(tempArr.size()>0){

System.out.println(tempArr);

}

return;

}

PrintSequences(arr, index+1, tempArr);

tempArr.add(arr[index]);

PrintSequences(arr, index+1, tempArr);

tempArr.remove(tempArr.size()-1);

}

public class PrintAllSequences {

public static void main(String[] args) {

int arr[]={1,2};

Solution1.PrintSequences(arr,0,new ArrayList<>());

}

Hierarchy Tree for arr = {1, 2} for Print All Subsequences of an Array

(1) PrintSequences(arr, 0, []) [tempArr=[], index=0, arr.length=2]

├── if(0 == arr.length) -> false

├── Recursion Left: (Skipping arr[0])

│ └── (2) PrintSequences(arr, 1, []) [tempArr=[], index=1, arr.length=2]

│ ├── if(1 == arr.length) -> false

│ ├── Recursion Left: (Skipping arr[1])

│ │ └── (3) PrintSequences(arr, 2, []) [tempArr=[], index=2, arr.length=2]

│ │ └── if(2 == arr.length) -> true (tempArr is empty, no output)

│ └── Recursion Right: (Including arr[1] = 2 in tempArr)

│ └── tempArr.add(2) -> tempArr = [2]

│ └── (4) PrintSequences(arr, 2, [2]) [tempArr=[2], index=2, arr.length=2]

│ └── if(2 == arr.length) -> true (print [2])

│ └── tempArr.remove(2) -> tempArr = [], tempArr.size()-1 = -1

└── Recursion Right: (Including arr[0] = 1 in tempArr)

└── tempArr.add(1) -> tempArr = [1]

└── (5) PrintSequences(arr, 1, [1]) [tempArr=[1], index=1, arr.length=2]

├── if(1 == arr.length) -> false

├── Recursion Left: (Skipping arr[1])

│ └── (6) PrintSequences(arr, 2, [1]) [tempArr=[1], index=2, arr.length=2]

│ └── if(2 == arr.length) -> true (print [1])

└── Recursion Right: (Including arr[1] = 2 in tempArr)

└── tempArr.add(2) -> tempArr = [1, 2]

└── (7) PrintSequences(arr, 2, [1, 2]) [tempArr=[1, 2], index=2, arr.length=2]

└── if(2 == arr.length) -> true (print [1, 2])

└── tempArr.remove(2) -> tempArr = [1], tempArr.size()-1 = 0

└── tempArr.remove(1) -> tempArr = [], tempArr.size()-1 = -1