DEV Community 👩‍💻👨‍💻

Prashant Mishra
Prashant Mishra

Posted on

Recursion

Subset sum

TC: O(2^n) as we have to two choices at every index of the arr either to take that index or not


//User function Template for Java//User function Template for Java
class Solution{
    ArrayList<Integer> subsetSums(ArrayList<Integer> arr, int N){
        // code here
        ArrayList<Integer> list = new ArrayList<>();
        getSum(N-1,arr,0,list);
        return list;
    }
    public void getSum(int index,List<Integer> arr,int sum,ArrayList<Integer> list){
        if(index<0){
            list.add(sum);
            return ;
        }
        //take
        sum+=arr.get(index);
        getSum(index-1,arr,sum,list);
        sum-=arr.get(index);
        getSum(index-1,arr,sum,list);
        //donttake
    }
}
Enter fullscreen mode Exit fullscreen mode

Subset sum II

Tc: O(2^n)*k, where k is the size of the subsets that you would need to put into list (as putting subsets in list is not constant hence assuming that the average length of the subset l is k)

import java.util.* ;
import java.io.*; 
public class Solution {
    public static ArrayList<ArrayList<Integer>> uniqueSubsets(int n, int arr[]) {
        Arrays.sort(arr);
        ArrayList<ArrayList<Integer>> list=  new ArrayList<>();
        getUnique(0,arr,new ArrayList<>(),list);
        return list;
    }
    public static void getUnique(int index,int arr[],ArrayList<Integer> l,ArrayList<ArrayList<Integer>> list){
        list.add(new ArrayList<>(l));
        for(int i = index;i<arr.length;i++){
            if( index!=i && arr[i] == arr[i-1]) continue;
            l.add(arr[i]);
            getUnique(i+1,arr,l,list);
            l.remove(l.size()-1);
        }
    }

}
Enter fullscreen mode Exit fullscreen mode

Combination sum i.e. using concept of subset sum I

Tc: O(2^n)*k where exponential for using recursion and for every call stack we will be adding subset(of assumed average length of k) in to list


import java.util.*;
public class Solution 
{
    public static ArrayList<ArrayList<Integer>> findSubsetsThatSumToK(ArrayList<Integer> arr, int n, int k) 
    {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        getSums(0,arr,new ArrayList<>(),k,list);
        return list;
    }
    public static void getSums(int index,ArrayList<Integer> arr,ArrayList<Integer> l,int target,ArrayList<ArrayList<Integer>> list){
        if(index>=arr.size()){ 
            if(target==0) list.add(new ArrayList<>(l));
            return;
        }
        //take
        l.add(arr.get(index));
        getSums(index+1,arr, l,target-arr.get(index),list);
        l.remove(l.size()-1);
        //dontTake
        getSums(index+1,arr,l,target,list);
    }
}
Enter fullscreen mode Exit fullscreen mode

Combination sum II i.e. using the concept of subset sum II

TC: O(2^n) *K, same as combination I

import java.util.*;

public class Solution 
{
    public static ArrayList<ArrayList<Integer>> combinationSum2(ArrayList<Integer> arr, int n, int target)
    {
        Collections.sort(arr);
        ArrayList<ArrayList<Integer>> list  = new ArrayList<>();
        getUniqueSubsetEqualsTarget(0,arr,target,new ArrayList<>(),list);
        return list;
    }
    public static void getUniqueSubsetEqualsTarget(int index,ArrayList<Integer> arr,int target,ArrayList<Integer> l,ArrayList<ArrayList<Integer>> list){
        if(target==0) list.add(new ArrayList<>(l));
        for(int i = index;i<arr.size();i++){
            if(i!=index && arr.get(i)==arr.get(i-1)) continue;
            if(arr.get(i)<=target){
                l.add(arr.get(i));
                getUniqueSubsetEqualsTarget(i+1,arr,target-arr.get(i),l,list);
                l.remove(l.size()-1);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Palindrome patitioning

TC: O(2^n)*k because of the same approach as Combination sum

import java.util.* ;
import java.io.*; 
public class Solution {
    public static List<List<String>> partition(String s) {
        // Write your code here.
        List<List<String>> list = new ArrayList<>();
        getAllPalindromicSubstrings(0,s,new ArrayList<>(),list);
        return list;
    }
    public static void getAllPalindromicSubstrings(int index, String s,
                                                  List<String> l,List<List<String>> list){
        if(index>=s.length()){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = index;i<s.length();i++){
            if(!isPalindrome(index,i,s)) continue;
            l.add(s.substring(index,i+1));
            getAllPalindromicSubstrings(i+1,s,l,list);
            l.remove(l.size()-1);
        }
    }
    public static boolean isPalindrome(int start,int end, String s){
        while(start<=end){
            if(s.charAt(start++)!=s.charAt(end--)) return false;
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

Kth Permutation sequence

TC: O(2^n)

import java.util.*;

public class Solution {
    static ArrayList<Integer> l;
    static int count;
    public static String kthPermutation(int n, int k) {
        l  = null;
        count = 0;
        int arr[] = new int[n];
        for(int i =0;i<arr.length;i++){
            arr[i] = i+1;
        }
        boolean check[] = new boolean[arr.length];
        String s = "";
        if(getAllPermutations(arr,new ArrayList<>(), check, k))
        for(Integer i : l){
            s+=i;
        }
        return s;
    }

    public static boolean getAllPermutations(int[] arr, List<Integer> list, boolean[] check, int k){
        if(list.size()==arr.length){
            count++;
            if(count ==k){
                l = new ArrayList<>(list);
                return true;
            }
        }
        for(int i =0;i<arr.length;i++){
            if(!check[i]){
                check[i] = true;
                list.add(arr[i]);
                if(getAllPermutations(arr,list,check,k)) return true;
                list.remove(list.size()-1);
                check[i] = false;
            }
        }
        return false;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

16 Libraries You Should Know as a React Developer

Being a modern React developer is not about knowing just React itself. To stay competitive, it is highly recommended to explore the whole ecosystem. This article contains some of the most useful React component libraries to speed up your developer workflow.