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)