Subsequence Patterns | Power Set | Subsets

Pattern 1 - Find all Subsequences

Given an integer array nums of unique elements, return all possible (link) subsets

(the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Solution

Recursive Approach

Take & Not-Take

We start with an empty list and iterate through each index, adding the element at position (index - i) to explore all possible combinations. Similarly, we remove the element at index (i) and explore all resulting possibilities. Finally, upon reaching the end, we create a new list and add it to the answer list.

Time - O(2^n)

Space - O(n)

class Solution {
    public void powerSet(int[] nums, int index, List<Integer> set, List<List<Integer>> ans){
        if(index>=nums.length){
            ans.add(new ArrayList<>(set));
            return;
        }
        set.add(nums[index]);
        powerSet(nums,index+1, set, ans);
        set.remove(set.size()-1);
        powerSet(nums,index+1, set, ans);
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> set = new ArrayList<>();
        powerSet(nums,0, set, ans);
        return ans;
    }
}

Recursive Tree

Pattern 2 -Print all Subsequences whose sum is K

Example

Input: arr = [1,2,1], sum = 2
Output: [[1,1],[2]]

Code

    public static void printSub(int[] arr, int index, int currentSum, int sum, List<Integer> currentSub, List<List<Integer>> ans){
        if(index == arr.length){
            if (currentSum==sum){
                ans.add(new ArrayList<>(currentSub));
            }
            return;
        }
        currentSub.add(arr[index]);
        currentSum+=arr[index];
        printSub(arr,index+1,currentSum,sum,currentSub,ans);
        currentSub.remove(currentSub.size()-1);
        currentSum-=arr[index];
        printSub(arr,index+1,currentSum,sum,currentSub,ans);
    }

Caller code

public static void main(String[] args) {
    int arr[] = {1,2,1};
    int sum = 2;
    List<List<Integer>> ans = new ArrayList<>();
    printSub(arr,0,0,sum,new ArrayList<>(),ans);
    System.out.println(ans);
}
/*
[[1, 1], [2]]
*/

Recursive Tree

Pattern 3 - Print any subsequence whose sum is target sum

Example

Input: arr = [1,2,1], sum = 2
Output: [1,1]

Code

public static boolean printSub(int[] arr, int index, int currentSum, int sum, List<Integer> currentSub){
    if(index == arr.length){
        if (currentSum==sum){
            return true;
        }
        return false;
    }
    currentSub.add(arr[index]);
    currentSum+=arr[index];
    if (printSub(arr,index+1,currentSum,sum,currentSub)) return true;
    currentSub.remove(currentSub.size()-1);
    currentSum-=arr[index];
    if(printSub(arr,index+1,currentSum,sum,currentSub)) return true;
    return false;
}

Caller

public static void main(String[] args) {
    int arr[] = {1,2,1};
    int sum = 2;
    List<Integer> currentSub = new ArrayList<>();
    printSub(arr,0,0,sum,currentSub);
    System.out.println(currentSub);
}
/*
[1, 1]
*/

Recursive Tree

Pattern 4 -Count the Subsequences with Sum k

Example

Input: arr = [1,2,1], sum = 2
Output: 2

Code

public static int countSub(int[] arr, int index, int currentSum, int sum){
    if(index == arr.length){
        if (currentSum==sum){
            return 1;
        }
        return 0;
    }
    currentSum+=arr[index];
    int leftCount = countSub(arr, index+1, currentSum,sum);
    currentSum-=arr[index];
    int rightCount = countSub(arr, index+1, currentSum, sum);
    return leftCount+rightCount;
}

Caller

public static void main(String[] args) {
    int arr[] = {1,2,1};
    int sum = 2;

    int count = countSub(arr,0,0,sum);
    System.out.println(count);
}

Recursive Tree

Complexity

• Time: (O(2^n)) - This accounts for all possible subsequence patterns.

• Space: (O(n)) - Auxiliary stack space, corresponding to the height of the tree (n).