Problem

Given an array write an algorithm to get or print all the possible sub subsequences.

Examples

Example 1:

1
2

Input: arr: [1, 2, 3] 
Output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Solution

Method 1 - Bit manipulation and recursion

To generate all possible subsequences, we can use a recursive approach or an iterative approach using bit manipulation:

  1. Recursive Approach:
    • For each element, we have two choices: either include the element in the current subsequence or exclude it.
    • Recursively generate subsequences for both choices.
  2. Iterative Approach using Bit Manipulation:
    • Each subsequence can be represented by a binary number where each bit represents whether the corresponding element is included in the subsequence.
    • Iterate through all numbers from 0 to 2^n - 1 (where n is the length of the array), and for each number, generate the subsequence corresponding to its binary representation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public List<List<Integer>> getAllSubsequences(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        generateSubsequences(arr, 0, new ArrayList<>(), result);
        return result;
    }

    private void generateSubsequences(int[] arr, int index,
        List<Integer> current, List<List<Integer>> result) {
        // Base case: add the current subsequence to the result
        if (index == arr.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Exclude the current element and move to the next
        generateSubsequences(arr, index + 1, current, result);

        // Include the current element and move to the next
        current.add(arr[index]);
        generateSubsequences(arr, index + 1, current, result);
        current.remove(current.size() - 1); // backtrack
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 2};
        List<List<Integer>> subsequences = solution.getAllSubsequences(arr);
        System.out.println(
            subsequences); // Expected output: [[], [1], [2], [1, 2]]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def getAllSubsequences(self, arr: List[int]) -> List[List[int]]:
        result = []
        self.generateSubsequences(arr, 0, [], result)
        return result

    def generateSubsequences(
        self,
        arr: List[int],
        index: int,
        current: List[int],
        result: List[List[int]],
    ):
        # Base case: add the current subsequence to the result
        if index == len(arr):
            result.append(list(current))
            return

        # Exclude the current element and move to the next
        self.generateSubsequences(arr, index + 1, current, result)

        # Include the current element and move to the next
        current.append(arr[index])
        self.generateSubsequences(arr, index + 1, current, result)
        current.pop()  # backtrack


# Example usage
sol = Solution()
arr = [1, 2]
subsequences = sol.getAllSubsequences(arr)
print(subsequences)  # Expected output: [[], [1], [2], [1, 2]]

Complexity

  • ⏰ Time complexity: O(n. 2^n), This is because there are (2^n) subsequences for an array of length n, and generating each subsequence takes O(n) time.
  • 🧺 Space complexity: O(n. 2^n), for storing all subsequences.